编辑“︁最大堆与最小堆”︁（章节）

= 最大堆与最小堆 =

'''最大堆（Max Heap）'''和'''最小堆（Min Heap）'''是两种特殊的[[二叉树]]结构，属于[[优先队列]]的常见实现方式。它们满足'''堆性质'''（Heap Property），即父节点与子节点之间存在特定的大小关系。最大堆中，父节点的值总是大于或等于其子节点的值；最小堆中，父节点的值总是小于或等于其子节点的值。堆结构常用于高效地获取、插入和删除极值元素（最大值或最小值）。

== 堆的性质 ==

堆是一种'''完全二叉树'''（Complete Binary Tree），即除了最后一层外，其他层都被完全填满，且最后一层的节点尽可能靠左排列。堆的主要性质如下：

* '''最大堆性质'''：对于任意节点 <math>i</math>，其值 <math>A[i] \geq A[2i]</math> 且 <math>A[i] \geq A[2i+1]</math>（如果子节点存在）。
* '''最小堆性质'''：对于任意节点 <math>i</math>，其值 <math>A[i] \leq A[2i]</math> 且 <math>A[i] \leq A[2i+1]</math>（如果子节点存在）。

堆通常用数组实现，其中：
* 根节点存储在索引 <math>1</math>（或 <math>0</math>，取决于实现）。
* 对于节点 <math>i</math>，其左子节点为 <math>2i</math>，右子节点为 <math>2i+1</math>，父节点为 <math>\lfloor i/2 \rfloor</math>。

== 堆的操作 ==

=== 插入元素（Heapify Up） ===
新元素插入到堆的末尾，然后通过与其父节点比较并交换（如果需要），逐步向上调整，直到满足堆性质。

=== 删除极值元素（Heapify Down） ===
删除堆顶元素（最大值或最小值），将最后一个元素移到堆顶，然后通过与其子节点比较并交换（如果需要），逐步向下调整，直到满足堆性质。

=== 构建堆 ===
从最后一个非叶子节点开始，依次对每个节点执行向下调整（Heapify Down），最终构建一个合法的堆。

== 代码示例 ==

以下是用 Python 实现最大堆和最小堆的代码示例：

=== 最大堆实现 ===
<syntaxhighlight lang="python">
class MaxHeap:
    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 insert(self, key):
        self.heap.append(key)
        i = len(self.heap) - 1
        while i > 0 and self.heap[i] > self.heap[self.parent(i)]:
            self.heap[i], self.heap[self.parent(i)] = self.heap[self.parent(i)], self.heap[i]
            i = self.parent(i)

    def extract_max(self):
        if not self.heap:
            return None
        max_val = self.heap[0]
        self.heap[0] = self.heap[-1]
        self.heap.pop()
        self.heapify_down(0)
        return max_val

    def heapify_down(self, i):
        left = self.left_child(i)
        right = self.right_child(i)
        largest = i
        if left < len(self.heap) and self.heap[left] > self.heap[largest]:
            largest = left
        if right < len(self.heap) and self.heap[right] > self.heap[largest]:
            largest = right
        if largest != i:
            self.heap[i], self.heap[largest] = self.heap[largest], self.heap[i]
            self.heapify_down(largest)

# 示例用法
max_heap = MaxHeap()
max_heap.insert(10)
max_heap.insert(5)
max_heap.insert(20)
max_heap.insert(1)
print("Max heap elements extracted in order:")
print(max_heap.extract_max())  # 输出 20
print(max_heap.extract_max())  # 输出 10
print(max_heap.extract_max())  # 输出 5
print(max_heap.extract_max())  # 输出 1
</syntaxhighlight>

=== 最小堆实现 ===
<syntaxhighlight lang="python">
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 insert(self, key):
        self.heap.append(key)
        i = len(self.heap) - 1
        while i > 0 and self.heap[i] < self.heap[self.parent(i)]:
            self.heap[i], self.heap[self.parent(i)] = self.heap[self.parent(i)], self.heap[i]
            i = self.parent(i)

    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.heapify_down(0)
        return min_val

    def heapify_down(self, i):
        left = self.left_child(i)
        right = self.right_child(i)
        smallest = i
        if left < len(self.heap) and self.heap[left] < self.heap[smallest]:
            smallest = left
        if right < len(self.heap) and self.heap[right] < self.heap[smallest]:
            smallest = right
        if smallest != i:
            self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
            self.heapify_down(smallest)

# 示例用法
min_heap = MinHeap()
min_heap.insert(10)
min_heap.insert(5)
min_heap.insert(20)
min_heap.insert(1)
print("Min heap elements extracted in order:")
print(min_heap.extract_min())  # 输出 1
print(min_heap.extract_min())  # 输出 5
print(min_heap.extract_min())  # 输出 10
print(min_heap.extract_min())  # 输出 20
</syntaxhighlight>

== 堆的可视化 ==

以下是一个最大堆的示例（使用 Mermaid 绘制）：

<mermaid>
graph TD
    20 --> 10
    20 --> 5
    10 --> 1
    10 --> 7
</mermaid>

* 根节点 20 是最大值。
* 每个父节点的值都大于或等于其子节点的值。

== 实际应用场景 ==

堆在以下场景中非常有用：

1. '''优先队列'''：堆是优先队列的高效实现方式，例如任务调度系统（总是执行优先级最高的任务）。
2. '''堆排序'''：利用最大堆或最小堆进行排序，时间复杂度为 <math>O(n \log n)</math>。
3. '''Dijkstra 算法'''：在图的最短路径算法中，最小堆用于高效获取当前距离最小的节点。
4. '''Top-K 问题'''：例如从海量数据中找出前 K 个最大或最小的元素。

== 时间复杂度分析 ==

堆的主要操作时间复杂度如下：
* 插入元素（Insert）：<math>O(\log n)</math>
* 删除极值元素（Extract-Max/Min）：<math>O(\log n)</math>
* 获取极值（Peek）：<math>O(1)</math>
* 构建堆（Heapify）：<math>O(n)</math>

== 总结 ==

最大堆和最小堆是高效管理动态数据极值的重要数据结构。它们的核心思想是通过维护堆性质，使得插入、删除和获取极值操作的时间复杂度保持在 <math>O(\log n)</math>。理解堆的实现和应用场景，对于解决优先队列相关问题和优化算法性能非常有帮助。

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:非线性数据结构]]