二叉堆（Binary Heap）的原理与实现

题目描述
二叉堆是一种特殊的完全二叉树，满足堆性质：每个节点的值都大于等于或小于等于其子节点的值。前者称为大顶堆（最大堆），后者称为小顶堆（最小堆）。二叉堆通常用于实现优先队列，支持插入、删除堆顶元素等操作，时间复杂度为O(log n)。要求理解其结构特性、存储方式，并能够手写插入和删除操作。

核心知识点

1. 完全二叉树性质：除最后一层外，其他层节点数达到最大值，且最后一层节点靠左排列。
2. 堆性质：父节点值 ≥（或 ≤）子节点值。
3. 数组存储：利用数组下标关系模拟树结构（下标从0或1开始）。
4. 上浮（Sift Up）与下沉（Sift Down）：维护堆性质的核心操作。

解题过程详解

步骤1：理解二叉堆的存储结构

• 使用数组存储完全二叉树，节省指针空间。
• 下标关系（假设下标从0开始）：
  • 父节点索引：parent(i) = (i - 1) // 2
  • 左子节点索引：left_child(i) = 2*i + 1
  • 右子节点索引：right_child(i) = 2*i + 2
• 示例：数组 [10, 7, 8, 5, 3] 对应的大顶堆：

        10
       /  \
      7    8
     / \
    5   3
  

步骤2：插入操作与上浮（Sift Up）
目标：将新元素插入堆尾，通过上浮调整至正确位置。
流程：

1. 将新元素追加到数组末尾（堆尾）。
2. 比较新元素与其父节点的值：
   • 若为大顶堆且新元素值 > 父节点值，则交换两者位置。
   • 重复步骤2，直到新元素值 ≤ 父节点值或到达根节点。

示例：向大顶堆 [10, 7, 8, 5, 3] 插入元素 9：

• 初始：[10, 7, 8, 5, 3, 9] → 9的父节点是3（下标2），9 > 3，交换 → [10, 7, 8, 5, 9, 3]
• 继续：9的父节点是7（下标1），9 > 7，交换 → [10, 9, 8, 5, 7, 3]
• 继续：9的父节点是10（下标0），9 ≤ 10，停止。最终堆为 [10, 9, 8, 5, 7, 3]。

步骤3：删除堆顶操作与下沉（Sift Down）
目标：删除堆顶元素后，将堆尾元素移至堆顶，通过下沉调整至正确位置。
流程：

1. 用堆尾元素替换堆顶元素，并删除堆尾。
2. 从堆顶开始，比较当前节点与其子节点的值：
   • 若为大顶堆，选择值较大的子节点。
   • 若当前节点值 < 子节点值，则交换两者位置。
3. 重复步骤2，直到当前节点值 ≥ 子节点值或成为叶子节点。

示例：从大顶堆 [10, 9, 8, 5, 7, 3] 删除堆顶元素10：

• 用堆尾元素3替换堆顶：[3, 9, 8, 5, 7]
• 下沉：3与子节点9和8比较，9较大，3 < 9，交换 → [9, 3, 8, 5, 7]
• 继续：3与子节点5和7比较，7较大，3 < 7，交换 → [9, 7, 8, 5, 3]
• 继续：3无子节点，停止。最终堆为 [9, 7, 8, 5, 3]。

步骤4：代码实现（大顶堆）

class MaxHeap:
    def __init__(self):
        self.heap = []
    
    def insert(self, val):
        self.heap.append(val)
        self._sift_up(len(self.heap) - 1)
    
    def pop_max(self):
        if not self.heap:
            return None
        max_val = self.heap[0]
        self.heap[0] = self.heap[-1]
        self.heap.pop()
        self._sift_down(0)
        return max_val
    
    def _sift_up(self, idx):
        while idx > 0:
            parent = (idx - 1) // 2
            if self.heap[idx] <= self.heap[parent]:
                break
            self.heap[idx], self.heap[parent] = self.heap[parent], self.heap[idx]
            idx = parent
    
    def _sift_down(self, idx):
        n = len(self.heap)
        while idx * 2 + 1 < n:  # 至少有左子节点
            left = idx * 2 + 1
            right = idx * 2 + 2
            max_child = left
            if right < n and self.heap[right] > self.heap[left]:
                max_child = right
            if self.heap[idx] >= self.heap[max_child]:
                break
            self.heap[idx], self.heap[max_child] = self.heap[max_child], self.heap[idx]
            idx = max_child

关键点总结

• 上浮用于插入操作，从底部向上调整。
• 下沉用于删除堆顶操作，从顶部向下调整。
• 时间复杂度：插入和删除均为O(log n)，建堆为O(n)（通过自底向上构建）。
• 应用场景：优先队列、Top K问题、堆排序等。