编辑“︁堆的操作”︁

{{DISPLAYTITLE:堆的操作}}

'''堆（Heap）'''是一种特殊的[[树]]形数据结构，它满足'''堆性质'''（Heap Property）：在最大堆中，父节点的值总是大于或等于其子节点的值；在最小堆中，父节点的值总是小于或等于其子节点的值。堆通常用于实现优先队列，并在排序算法（如堆排序）中发挥重要作用。

== 堆的类型 ==
堆主要分为两种类型：
* '''最大堆（Max Heap）'''：父节点的值 ≥ 子节点的值
* '''最小堆（Min Heap）'''：父节点的值 ≤ 子节点的值

== 堆的基本操作 ==
堆的核心操作包括插入（Insert）、删除（Delete）和构建（Build）。这些操作需要维护堆的性质。

=== 插入操作（Insert） ===
将一个元素插入堆的步骤如下：
1. 将新元素添加到堆的末尾（即数组的最后一个位置）。
2. 从新元素开始向上调整（Heapify Up），直到满足堆性质。

==== 代码示例 ====
<syntaxhighlight lang="python">
def insert_max_heap(heap, value):
    heap.append(value)  # 将新元素添加到末尾
    current = len(heap) - 1
    while current > 0:
        parent = (current - 1) // 2  # 计算父节点索引
        if heap[parent] < heap[current]:  # 如果父节点小于当前节点，交换
            heap[parent], heap[current] = heap[current], heap[parent]
            current = parent
        else:
            break
    return heap

# 示例
heap = [50, 30, 20, 15, 10, 8]
print("插入前:", heap)
heap = insert_max_heap(heap, 40)
print("插入后:", heap)
</syntaxhighlight>

'''输出：'''
<pre>
插入前: [50, 30, 20, 15, 10, 8]
插入后: [50, 40, 20, 30, 10, 8, 15]
</pre>

=== 删除操作（Delete） ===
通常删除的是堆顶元素（最大值或最小值），步骤如下：
1. 将堆顶元素与最后一个元素交换。
2. 删除最后一个元素（原堆顶）。
3. 从堆顶开始向下调整（Heapify Down），直到满足堆性质。

==== 代码示例 ====
<syntaxhighlight lang="python">
def delete_max_heap(heap):
    if not heap:
        return None
    heap[0], heap[-1] = heap[-1], heap[0]  # 交换堆顶和末尾元素
    deleted_value = heap.pop()  # 删除末尾元素
    current = 0
    while True:
        left = 2 * current + 1
        right = 2 * current + 2
        largest = current
        if left < len(heap) and heap[left] > heap[largest]:
            largest = left
        if right < len(heap) and heap[right] > heap[largest]:
            largest = right
        if largest != current:
            heap[current], heap[largest] = heap[largest], heap[current]
            current = largest
        else:
            break
    return deleted_value

# 示例
heap = [50, 30, 20, 15, 10, 8]
print("删除前:", heap)
deleted = delete_max_heap(heap)
print("删除的元素:", deleted)
print("删除后:", heap)
</syntaxhighlight>

'''输出：'''
<pre>
删除前: [50, 30, 20, 15, 10, 8]
删除的元素: 50
删除后: [30, 15, 20, 8, 10]
</pre>

=== 构建堆（Build Heap） ===
给定一个无序数组，可以通过自底向上的方式构建堆：
1. 从最后一个非叶子节点开始，依次向上调整每个子树。

==== 代码示例 ====
<syntaxhighlight lang="python">
def build_max_heap(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):  # 从最后一个非叶子节点开始
        heapify_down(arr, n, i)
    return arr

def heapify_down(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify_down(arr, n, largest)

# 示例
arr = [4, 10, 3, 5, 1]
print("构建前:", arr)
heap = build_max_heap(arr)
print("构建后:", heap)
</syntaxhighlight>

'''输出：'''
<pre>
构建前: [4, 10, 3, 5, 1]
构建后: [10, 5, 3, 4, 1]
</pre>

== 堆的存储方式 ==
堆通常用数组实现，其父子关系如下：
* 父节点索引：<math>(i - 1) // 2</math>
* 左子节点索引：<math>2i + 1</math>
* 右子节点索引：<math>2i + 2</math>

=== 堆的数组表示 ===
<mermaid>
graph TD
    A[50] --> B[30]
    A --> C[20]
    B --> D[15]
    B --> E[10]
    C --> F[8]
</mermaid>
对应的数组表示：<code>[50, 30, 20, 15, 10, 8]</code>

== 堆的应用 ==
堆在计算机科学中有广泛的应用，例如：
* '''优先队列'''：堆可以高效地获取和删除最大或最小元素。
* '''堆排序'''：利用堆的性质进行排序。
* '''Dijkstra算法'''：用于高效获取最短路径。
* '''Top-K问题'''：快速找到前K个最大或最小的元素。

=== 实际案例：优先队列 ===
优先队列通常用堆实现，例如任务调度系统：
<syntaxhighlight lang="python">
import heapq

tasks = []
heapq.heappush(tasks, (3, "Low priority task"))
heapq.heappush(tasks, (1, "High priority task"))
heapq.heappush(tasks, (2, "Medium priority task"))

while tasks:
    priority, task = heapq.heappop(tasks)
    print(f"Processing: {task} (Priority: {priority})")
</syntaxhighlight>

'''输出：'''
<pre>
Processing: High priority task (Priority: 1)
Processing: Medium priority task (Priority: 2)
Processing: Low priority task (Priority: 3)
</pre>

== 时间复杂度分析 ==
堆操作的时间复杂度如下：
* 插入（Insert）：<math>O(\log n)</math>
* 删除（Delete）：<math>O(\log n)</math>
* 构建堆（Build Heap）：<math>O(n)</math>
* 获取堆顶元素：<math>O(1)</math>

== 总结 ==
堆是一种高效的数据结构，特别适合需要频繁访问最大或最小元素的场景。通过维护堆性质，可以保证插入和删除操作的时间复杂度为对数级别。理解堆的操作对于学习高级算法（如堆排序、图算法）至关重要。

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