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

1. 二叉堆的定义与基本性质
二叉堆是一种完全二叉树（Complete Binary Tree），满足以下性质：

• 结构性：所有层除最后一层外都是满的，最后一层节点尽量靠左排列。
• 堆序性：
  • 最大堆：每个节点的值大于或等于其子节点的值（根节点最大）。
  • 最小堆：每个节点的值小于或等于其子节点的值（根节点最小）。

关键点：完全二叉树的结构允许用数组高效存储，无需指针。若数组下标从0开始，对于节点i：

• 父节点下标：(i-1)//2
• 左子节点下标：2*i+1
• 右子节点下标：2*i+2

2. 二叉堆的核心操作
（1）插入元素（Insert）
步骤：

1. 将新元素添加到数组末尾（完全二叉树的最后一个位置）。
2. 上浮（Sift Up）：比较新节点与其父节点的值，若违反堆序性（如最小堆中父节点更大），则交换两者，重复此过程直到根节点或满足堆序。

示例（最小堆）：插入元素2

初始堆：[3, 5, 7, 9, 6, 8]  
插入后：[3, 5, 7, 9, 6, 8, 2]  
上浮过程：  
  2（位置6）与父节点7（位置2）比较 → 交换 → [3, 5, 2, 9, 6, 8, 7]  
  2（位置2）与父节点3（位置0）比较 → 交换 → [2, 5, 3, 9, 6, 8, 7]  

时间复杂度：O(log n)，因树高为log n。

（2）删除堆顶元素（Extract-Min/Max）
步骤：

1. 取出堆顶元素（根节点）。
2. 将数组末尾元素移到堆顶。
3. 下沉（Sift Down）：比较新根节点与其子节点，若违反堆序性（如最小堆中子节点更小），则与较小的子节点交换，重复直到满足堆序。

示例（最小堆）：删除堆顶2

初始堆：[2, 5, 3, 9, 6, 8, 7]  
交换堆顶与末尾：[7, 5, 3, 9, 6, 8]  
下沉过程：  
  7（位置0）与子节点3（位置2）和5（位置1）比较 → 与3交换 → [3, 5, 7, 9, 6, 8]  
  7（位置2）与子节点8（位置5）比较 → 无需交换（已满足堆序）。

时间复杂度：O(log n)。

3. 堆的构建（Heapify）
问题：如何将无序数组快速转换为堆？
直接插入法：逐个插入元素，时间复杂度O(n log n)。
高效方法（Floyd算法）：从最后一个非叶子节点开始，自底向上逐节点下沉。

步骤：  
  1. 找到最后一个非叶子节点下标：`(n-2)//2`。  
  2. 从该节点到根节点，依次执行下沉操作。  

示例：数组[9, 5, 7, 3, 6, 8]

非叶子节点下标：2（值7）→ 1（值5）→ 0（值9）  
  下标2：7的子节点8，无需下沉。  
  下标1：5与子节点3交换 → [9, 3, 7, 5, 6, 8]  
  下标0：9与子节点3交换 → [3, 9, 7, 5, 6, 8]  
        9继续与子节点5交换 → [3, 5, 7, 9, 6, 8]  

时间复杂度：O(n)，分析需用等比数列求和（大部分节点高度较低）。

4. 堆的应用场景

• 优先队列：堆是实现优先队列（如Python的heapq）的理想结构。
• 堆排序：反复取出堆顶元素，时间复杂度O(n log n)。
• Top-K问题：用最小堆维护前K大元素（或最大堆维护前K小元素）。
• Dijkstra算法：用堆优化最短路径的节点选择。

5. 代码实现（最小堆）

class MinHeap:
    def __init__(self):
        self.heap = []
    
    def parent(self, i):
        return (i-1)//2
    
    def left_child(self, i):
        return 2*i+1
    
    def right_child(self, i):
        return 2*i+2
    
    def swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
    
    def insert(self, key):
        self.heap.append(key)
        self._sift_up(len(self.heap)-1)
    
    def _sift_up(self, i):
        while i > 0 and self.heap[i] < self.heap[self.parent(i)]:
            p = self.parent(i)
            self.swap(i, p)
            i = p
    
    def extract_min(self):
        if not self.heap:
            return None
        min_val = self.heap[0]
        self.heap[0] = self.heap[-1]
        self.heap.pop()
        self._sift_down(0)
        return min_val
    
    def _sift_down(self, i):
        n = len(self.heap)
        while True:
            left = self.left_child(i)
            right = self.right_child(i)
            smallest = i
            if left < n and self.heap[left] < self.heap[smallest]:
                smallest = left
            if right < n and self.heap[right] < self.heap[smallest]:
                smallest = right
            if smallest == i:
                break
            self.swap(i, smallest)
            i = smallest
    
    def build_heap(self, arr):
        self.heap = arr
        for i in range((len(arr)-2)//2, -1, -1):
            self._sift_down(i)

总结：二叉堆通过数组存储和堆序性维护，以O(log n)时间支持动态插入删除，是高效处理优先级问题的核心数据结构。