python 中的堆数据结构

Question

我已经在 python 中实现了最小堆，但经过一些测试后我意识到有时大约每 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()

我的最后 2 个小时一直在寻找错误，所以如果有人能帮助我，我将不胜感激。

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。它的 parent 应该是 1(index = 0)。但是 i//2 会给你 5(index = 1) 作为 2//2 = 1.

所以，你应该使用 (i-1)//2，这会给你 0.

(2-1)//2 = 0

希望您已经理解我的解决方案。

python 中的堆数据结构

Heap data structure in python

python

heap

data-structures

解决方案

说明