堆的操作

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

堆的类型

堆主要分为两种类型：

• 最大堆（Max Heap）：父节点的值 ≥ 子节点的值
• 最小堆（Min Heap）：父节点的值 ≤ 子节点的值

堆的基本操作

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

插入操作（Insert）

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

代码示例

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)

输出：

插入前: [50, 30, 20, 15, 10, 8]
插入后: [50, 40, 20, 30, 10, 8, 15]

删除操作（Delete）

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

代码示例

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)

输出：

删除前: [50, 30, 20, 15, 10, 8]
删除的元素: 50
删除后: [30, 15, 20, 8, 10]

构建堆（Build Heap）

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

代码示例

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)

输出：

构建前: [4, 10, 3, 5, 1]
构建后: [10, 5, 3, 4, 1]

堆的存储方式

堆通常用数组实现，其父子关系如下：

• 父节点索引：$(i-1)//2$
• 左子节点索引：$2i+1$
• 右子节点索引：$2i+2$

堆的数组表示

graph TD A[50] --> B[30] A --> C[20] B --> D[15] B --> E[10] C --> F[8]

对应的数组表示：[50, 30, 20, 15, 10, 8]

堆的应用

堆在计算机科学中有广泛的应用，例如：

• 优先队列：堆可以高效地获取和删除最大或最小元素。
• 堆排序：利用堆的性质进行排序。
• Dijkstra算法：用于高效获取最短路径。
• Top-K问题：快速找到前K个最大或最小的元素。

实际案例：优先队列

优先队列通常用堆实现，例如任务调度系统：

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})")

输出：

Processing: High priority task (Priority: 1)
Processing: Medium priority task (Priority: 2)
Processing: Low priority task (Priority: 3)

时间复杂度分析

堆操作的时间复杂度如下：

• 插入（Insert）：$O(\log n)$
• 删除（Delete）：$O(\log n)$
• 构建堆（Build Heap）：$O(n)$
• 获取堆顶元素：$O(1)$

总结

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