我的自定义 heapify 方法在 python 中无法正常工作

Question

我正在学习数据结构，但我的代码无法正常工作..我尝试调试但找不到任何东西（似乎 heapifyinsert() 没有做任何事情）

这是我的代码：

class Heap:
    def __init__(self,size):
        self.heap=[None]*(size+1)
        self.heapsize=0
        self.maxheapsize=size+1


    def levelordertransversal(self):
        if not self.heap:
            raise Exception('Heap doesn\'t exists')
        for x in range(1,self.heapsize+1):
            print(self.heap[x])

    def heapifyinsert(self,index,heaptype):
        heaptype=heaptype.title()
        parentindex=int(index/2)
        if parentindex<=1:
            return
        if heaptype=='Min':
            if self.heap[index]<self.heap[parentindex]:
                temp=self.heap[index]
                self.heap[index]=self.heap[parentindex]
                self.heap[parentindex]=temp
            self.heapifyinsert(parentindex,heaptype)
        elif heaptype=='Max':
            if self.heap[index]>self.heap[parentindex]:
                temp=self.heap[index]
                self.heap[index]=self.heap[parentindex]
                self.heap[parentindex]=temp
            self.heapifyinsert(parentindex,heaptype)

    def insertnode(self,nodevalue,heaptype):
        if self.heapsize+1==self.maxheapsize:
            raise Exception('Heap is full!!')
        self.heap[self.heapsize+1]=nodevalue
        self.heapsize+=1
        self.heapifyinsert(self.heapsize,heaptype)

h=Heap(5)
h.insertnode(4,'Max')
h.insertnode(5,'Max')
h.insertnode(2,'Max')
h.insertnode(1,'Max')
h.levelordertransversal()

当前输出：

预期输出：

所以在上面的代码中，我尝试从索引位置 1 开始实现堆（为了简单起见），在 heapifyinsert() 方法中，我们采用 parentindex 并检查父索引的值是否更大或更少根据堆类型和交换值

任何帮助或线索将不胜感激..谢谢！

Answer 1

问题是递归停止得太快了。 1 是堆中的有效索引，而 0 不是，因此这意味着您需要更改：

if parentindex<=1:

...至：

if parentindex< 1:

这将解决问题。

对您的代码的一些其他评论：

当child和parent比较成功时，递归可以停止。因此，将 self.heapifyinsert(parentindex,heaptype) 的调用移到前面的 if 块中。
不应为 insertnode 定义 heaptype 参数，因为显然为 insertnode 的下一次调用提供不同的值是没有意义的：它应该始终为“Min”或始终为“Max”。所以这应该是构造函数的参数并存储为堆的属性
在 Python 中，您可以使用元组赋值轻松交换值，而无需 temp 变量
int(index/2) 将首先执行浮点除法并将其转换回整数。仅使用整数除法更有意义：index // 2
if not self.heap: 是不必要的：因为 heap 属性是由构造函数初始化的，这永远不会发生
避免一些代码重复：交换和递归调用在堆类型上是相同的，因此请尝试重新安排您的代码，以便只编码一次。

我的自定义 heapify 方法在 python 中无法正常工作

my custom heapify method not working properly in python

python

heap

data-structures