Python实现Max_Heap最大堆逻辑错误排查求助

你的Max_Heap类插入元素后输出不符合预期，当前输出为46 12 11 10 6 2，期望结果为46,12,6,11,10,2。问题出在parent函数的索引计算上，以下是具体分析和修复方案：

错误原因 #

Python列表采用0起始索引，而你实现的parent函数使用pos // 2计算父节点索引，这是1起始堆的计算方式。对于0起始堆，父节点的正确索引公式应为(pos - 1) // 2。

这个错误会导致插入元素时，右子节点的父节点查找错误，进而改变元素上浮的路径，最终生成与预期结构不同的堆（虽然当前输出仍是合法的最大堆，但不符合你期望的标准结构）。另外原insert方法中缺少对current > 0的判断，当current为0时（根节点）继续访问父节点会导致重复比较根节点自身，虽不影响结果但存在逻辑冗余。

修复后的代码 #

class Max_Heap:
    def __init__(self):
        self.heap = []
        
    def parent(self, pos):
        return (pos - 1) // 2  # 修正父节点索引计算
    
    def left_c(self, pos):
        return (2 * pos) + 1
    
    def right_c(self, pos):
        return (2 * pos) + 2
    
    def swap(self, fpos, spos):
        self.heap[fpos], self.heap[spos] = self.heap[spos], self.heap[fpos]
    
    def insert(self, v):
        self.heap.append(v)
        current = len(self.heap) - 1
        # 增加current > 0判断，避免根节点无意义的比较
        while current > 0 and self.heap[current] > self.heap[self.parent(current)]:
            self.swap(current, self.parent(current))
            current = self.parent(current)
                
    def print_heap(self):
        for i in range(len(self.heap)):
            print(self.heap[i], end=' ')
        print('\n')

a = Max_Heap()
a.insert(10)
print('Printing heap.....')
a.print_heap()
print('Printing heap.....')
a.insert(12)
a.insert(6)
a.insert(11)
a.insert(46)
a.insert(2)
a.print_heap()

修复后输出 #

Printing heap.....
10 

Printing heap.....
46 12 6 11 10 2 

内容的提问来源于stack exchange，提问作者Vedant Bhosale