如何将_leftChild和_rightChild集成到最大二叉堆的deleteMax函数中

首先需要修正_leftChild和_rightChild的判断逻辑（原逻辑存在索引越界风险），然后修改deleteMax函数，通过转换为1-based索引调用这两个子节点方法完成堆调整。

修正后的完整代码 #

class MaxBinaryHeap:
  
    def __init__(self):
        self._heap=[]
        
    def __str__(self):
        return f'{self._heap}'

    __repr__=__str__

    def __len__(self):
        return len(self._heap)
    
    @property
    def getMax(self):
        if len(self) == 0:
            return None
        else:
            return self._heap[0]
        
    
    def _parent(self,index):
        if index <= 1 or index > len(self): 
            return None
        else: 
            return self._heap[(index // 2)-1]
        

    def _leftChild(self,index):
        # 修正判断条件：确保数组索引不越界
        left_idx = 2 * index - 1
        if left_idx < len(self._heap): 
            return self._heap[left_idx]
        else:
            return None


    def _rightChild(self,index):
        # 修正判断条件：确保数组索引不越界
        right_idx = 2 * index
        if right_idx < len(self._heap): 
            return self._heap[right_idx]
        else:
            return None
         

    def insert(self,x):
        self._heap.append(x)
        current = len(self._heap) - 1
        while self._parent(current + 1) is not None and self._heap[current] > self._parent(current + 1):
            parent_current = ((current + 1) // 2) -1
            self._heap[current], self._heap[parent_current] = self._heap[parent_current], self._heap[current]
            current = parent_current
           
        

    def deleteMax(self):
        if len(self) == 0:
            return None
        elif len(self) == 1:
            removed = self._heap[0]
            self._heap = []
            return removed

        max_value = self._heap[0]
        last_value = self._heap.pop()
        self._heap[0] = last_value

        current = 0  # 当前节点的0-based数组索引
        while True:
            # 转换为1-based节点编号，匹配_leftChild/_rightChild的参数要求
            current_1based = current + 1
            left_val = self._leftChild(current_1based)
            right_val = self._rightChild(current_1based)

            # 没有左孩子，说明已是叶子节点，结束调整
            if left_val is None:
                break

            # 确定要交换的子节点索引
            swap_idx = 2 * current + 1  # 左孩子的0-based索引
            # 如果存在右孩子且右孩子值更大，切换到右孩子索引
            if right_val is not None and right_val > left_val:
                swap_idx = 2 * current + 2

            # 如果当前节点值小于子节点值，执行交换
            if self._heap[current] < self._heap[swap_idx]:
                self._heap[current], self._heap[swap_idx] = self._heap[swap_idx], self._heap[current]
                current = swap_idx
            else:
                # 满足大顶堆性质，结束调整
                break

        return max_value

关键修改说明 #

1. 修正子节点方法的判断逻辑

   • _leftChild：原判断条件2*index < len(self)会漏掉左孩子刚好是最后一个节点的情况，改为直接计算数组索引left_idx = 2*index -1，判断其是否小于堆的长度，避免越界。
   • _rightChild：原判断条件(2*index)-1 < len(self)存在逻辑错误，改为计算右孩子的数组索引right_idx = 2*index，判断其是否小于堆的长度，确保不会访问不存在的数组元素。

2. 修改deleteMax调用子节点方法

   • 将当前节点的0-based数组索引转换为1-based编号（current_1based = current +1），匹配_leftChild和_rightChild的参数要求。
   • 通过_leftChild(current_1based)和_rightChild(current_1based)获取子节点的值，判断子节点是否存在。
   • 基于子节点的值比较，确定需要交换的子节点索引，完成堆的向下调整。

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