Python：治愈科德·敏希普？

Question

我正在为K阶最小堆创建一个类。我将堆存储为一个列表。我在实现remove_min时遇到问题。我知道移除最小堆的过程是：

1. 移除第一个元素。这是最低要求。

2. 交换第一个元素和最后一个元素。

3. 向下冒泡新的top元素，直到它满足heap属性。

所以我需要一个remove-min和一个助手函数，bubbledown。我不能使用heapq，因为它只考虑二进制堆，而这个类需要一个k阶堆。以下是我目前所掌握的情况：

class KHeap:
    def __init__(self, lst=[], k=2):
        self.heap = []
        self.k = k #order of heap
        for v in lst:
            self.insert(v)

    def children(self, i): #returns a list of the children of the item in index i
        heap = self.heap
        result = []
        for x in range(self.k*i+1, self.k*i+self.k+1):
            if x<len(heap):
                result.append(heap[x])
            else:
                pass
        return result

    def parent(self, i): #returns the parent of item in index i
        heap = self.heap
        if i==0:
            return None
        result = i//self.k
        return heap[result]

    def bubbleup(self, i): 
        if i == 0:
            return None
        elif self.heap[i] < self.parent(i):
            self.heap[i], self.heap[i // self.k] = self.heap[i // self.k], self.heap[i]
            self.bubbleup(i // self.k)

    def insert(self, value): #use bubbleup
        self.heap.append(value)
        self.bubbleup(len(self.heap)-1)

    def bubbledown(self, i, d=1):
        if i==0:
            return None
        small = i
        for k in range(self.children(i)):
            if self.heap[k]<self.heap[small]:
                small = k
        self.heap[i], self.heap[small] = self.heap[small], self.heap[i]
        self.bubbledown(small)

    def remove_min(self): #use bubbledown
        if len(self.heap) == 0:
            return None
        if len(self.heap) == 1:
            return self.heap.pop()
        minimum = self.heap[0]
        self.heap[0] = self.heap.pop()
        self.bubbledown(0)
        return minimum

现在，当我去掉逯min，结果是不好的。例如，如果我有一个三元堆[1, 10, 18, 22, 15, 30], k=3并去掉最小值，结果是[30, 10, 18, 22, 15]。似乎我移到顶端的元素永远不会泡汤。在

Answer 1

所以我发布了一个迭代版本，它可以解决I==0的问题。在

def bubbledown(self, i, d=1):
    small = i
    size = len(self.heap)
    while (i < size):
        // find the smallest child
        for k in range(self.children(i)):
            if self.heap[k] < self.heap[small]:
                small = k
        self.heap[i], self.heap[small] = self.heap[small], self.heap[i]
        // stop here
        if small == i:
            break
        else:
            i = small