使用列表无法满足 maxheap 属性

Question

我正在创建一个 MaxHeap class，我必须使用一个列表来完成它。我无法以正确的顺序将元素插入堆中以满足 maxheap 要求。我不允许向构造函数添加任何内容。我该怎么办？

class MaxHeap:  

    def __init__(self):
        self.Heap=[]

    def parent(self, pos): 
        return pos//2


    def leftChild(self, pos): 
        return 2 * pos 


    def rightChild(self, pos): 
        return (2 * pos) + 1

    def insert(self, element):
        self.Heap.append(element)
        child = len(self.Heap) - 1

        while child > 0:
            parent = self.parent(child)
            if self.Heap[parent] >= self.Heap[child]:
                return

            self.Heap[child], self.Heap[parent] = self.Heap[parent], self.Heap[child]
            child = parent

我的代码做了什么（左）与预期的（右）（用 | 分隔）

x = MaxHeap()

x.insert(10)

[10] | [10]

x.insert(5)

[10,5] | [10,5]

x.insert(14)

[14,10,5] | [14,5,10] -> 首先事情开始出错

x.insert(9)

[14,10,5,9] | [14,9,10,5] 我的代码又错了，其他的也一样

x.insert(2)

[14,10,5,9,2] | [14,9,10,5,2]

x.insert(11)

[14,11,10,9,2,5] | [14,9,11,5,2,10]

x.insert(6)

[14,11,10,9,2,5,6] | [14,9,11,5,2,10,6]

插入14时，初始是10的右child，然后你把14和10交换，堆的层级遍历就是数组表示，14就是parent， 5个左边child和10个右边child等等

当我最初加14时，它从[10,5]变为[10,5,14]

使用 [10,5,14]，我将 14 与它的 parent 进行比较，后者将是 10。这不满足最大堆属性，因此我必须将 10 切换为14，这样就变成了[14,5,10]

我会怎么做他的？

Answer 1

Python 列表的索引从 0 开始，但您使用的 parent/child 公式适用于以 1 为根的堆。

对于以 0 为根的堆：

leftChild(x) = x*2+1
rightChild(x) = x*2+2
parent(x) = (x-1)//2

使用列表无法满足 maxheap 属性

Having trouble satisfying the maxheap property using a list

python

heap

function

list

data-structures

我的代码做了什么（左）与预期的（右）（用 | 分隔）