使用列表难以满足maxheap属性

Question

我正在创建MaxHeap类，我必须使用列表来完成。我无法按照满足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的右子级。然后交换14和10，堆的层遍历是数组表示形式，14是父级，5是左子级，10是右子级，依此类推。

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

使用[10,5,14]，我将14与它的父级进行比较，该父级将为10。这不满足最大堆属性，因此我必须将10与14切换，以使其变为[14,5， 10]

我该怎么办？

Answer 1

Python列表的索引从0开始，但是您使用的父/子公式是针对以1为根的堆。

对于以0为根的堆：

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