python中的堆数据结构

Question

我已经在python中实现了min-heap，但是在一些测试之后，我意识到有时候大约每插入10次之后，它就会将其放在错误的位置（父对象比子对象大）。 守则：

class minHeap():
    def __init__(self):
        self.heap = [] # main array
        
    def get_parent(self, i):
        return i//2

    def bubble_up(self):
        i = len(self.heap)-1
        p = self.get_parent(i)
        while self.heap[p] > self.heap[i]:
            self.heap[i], self.heap[p] = self.heap[p], self.heap[i] # swapping parent and child
            i = p
            p = self.get_parent(i)

    def insert(self, k):
        self.heap.append(k)
        self.bubble_up()

我过去的两个小时一直在搜索这个bug，所以如果有人能帮助我，我会非常感激

Answer 1

解决方案

您应该将此函数从

def get_parent(self, i):
    return i//2

致：

def get_parent(self, i):
    return (i-1)//2

---

解释

您正在使用python中的一个列表进行初始化，它是0-indexed

self.heap = [] # main array

现在，假设您添加了2个元素1和5

self.heap = [1,5]

现在。如果您再添加一个元素，即3

self.heap = [1,5,3]

现在，3的索引是2。它的父项应该是1（索引=0）。但是i//2会给你5（索引=1）作为2//2 = 1

因此，您应该使用(i-1)//2，它将为您提供0

(2-1)//2 = 0

---

希望你理解我的解决方案🔑.

---