数据结构之堆：原理与实现

1. 什么是堆？

堆（Heap）是一种特殊的完全二叉树，它的每个节点都遵循以下性质之一：

• 最大堆（Max-Heap）：每个节点的值都大于等于其子节点的值，根节点是最大值。
• 最小堆（Min-Heap）：每个节点的值都小于等于其子节点的值，根节点是最小值。

堆的主要特点是便于快速获取最大值或最小值，因此堆广泛用于优先队列、堆排序等场景。

2. 堆的存储结构

堆通常用数组存储，其逻辑结构是树形，但存储方式是顺序存储（数组）。堆节点的索引关系如下：

• 父节点：索引为i的节点的父节点在索引(i-1)/2。
• 左子节点：索引为i的节点的左子节点在索引2*i+1。
• 右子节点：索引为i的节点的右子节点在索引2*i+2。

堆的数组表示示例： 对于完全二叉树：

​
          10
        /    \
      9        8
     / \      / \
    7   6    5   4
​

对应的数组存储为：[10, 9, 8, 7, 6, 5, 4]。

3. 堆的操作

堆的核心操作包括：

1. 插入（Insert）：在堆中添加新元素，并维护堆的性质。
2. 删除（Delete）：从堆中移除根节点（最大堆中的最大值或最小堆中的最小值），并维护堆的性质。
3. 堆化（Heapify）：调整堆以恢复堆性质，分为向上调整和向下调整。

其中向下调整如图：

4. 堆的实现

以下是用C语言实现最大堆的代码示例：

1. 堆的定义和初始化

​
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int *data;     // 数组存储堆的元素
    int size;      // 当前堆中元素数量
    int capacity;  // 堆的容量
} Heap;

// 初始化堆
Heap* createHeap(int capacity) {
    Heap* heap = (Heap*)malloc(sizeof(Heap));
    heap->data = (int*)malloc(sizeof(int) * capacity);
    heap->size = 0;
    heap->capacity = capacity;
    return heap;
}

​

2. 插入操作（Insert）

插入新元素时，需要将元素放到堆的最后，然后通过向上调整恢复堆的性质。

​
void insert(Heap* heap, int value) {
    if (heap->size >= heap->capacity) {
        printf("堆已满，无法插入元素。\n");
        return;
    }
    heap->data[heap->size] = value;  // 将新元素放在堆的末尾
    int i = heap->size;
    heap->size++;

    // 向上调整
    while (i > 0 && heap->data[i] > heap->data[(i-1)/2]) {
        // 如果当前节点大于父节点，交换两者
        int temp = heap->data[i];
        heap->data[i] = heap->data[(i-1)/2];
        heap->data[(i-1)/2] = temp;
        i = (i-1)/2;  // 更新当前节点为父节点
    }
}

​

3. 删除操作（Delete）

删除最大堆中的根节点（即最大值）时，需要将堆的最后一个元素放到根节点位置，并通过向下调整恢复堆的性质。

​
int deleteMax(Heap* heap) {
    if (heap->size <= 0) {
        printf("堆为空，无法删除元素。\n");
        return -1;
    }
    int maxValue = heap->data[0];  // 根节点的值即为最大值
    heap->data[0] = heap->data[heap->size - 1]; // 用最后一个元素替换根节点
    heap->size--;

    int i = 0;
    while (2*i+1 < heap->size) {  // 检查是否有左子节点
        int maxChild = 2*i+1;  // 假设左子节点为较大子节点
        if (2*i+2 < heap->size && heap->data[2*i+2] > heap->data[2*i+1]) {
            maxChild = 2*i+2;  // 如果右子节点更大，则更新为右子节点
        }
        if (heap->data[i] >= heap->data[maxChild]) {
            break;  // 如果当前节点大于等于较大子节点，堆已调整完毕
        }
        // 交换当前节点和较大子节点
        int temp = heap->data[i];
        heap->data[i] = heap->data[maxChild];
        heap->data[maxChild] = temp;
        i = maxChild;  // 更新当前节点为较大子节点
    }
    return maxValue;
}

​

4. 打印堆内容

​
void printHeap(Heap* heap) {
    for (int i = 0; i < heap->size; i++) {
        printf("%d ", heap->data[i]);
    }
    printf("\n");
}

​

5. 测试堆的操作

​
int main() {
    Heap* heap = createHeap(10);

    insert(heap, 15);
    insert(heap, 10);
    insert(heap, 30);
    insert(heap, 25);

    printf("当前堆: ");
    printHeap(heap);

    printf("删除最大值: %d\n", deleteMax(heap));
    printf("当前堆: ");
    printHeap(heap);

    free(heap->data);
    free(heap);

    return 0;
}

​

5. 堆的应用场景

1. 优先队列：基于堆实现的优先队列可以快速获取优先级最高的元素。
2. 堆排序：堆是一种高效的排序工具，时间复杂度为O(n log n)。
3. 图算法：在Dijkstra最短路径算法和Prim最小生成树算法中，堆用于高效选择最小权重边。
4. Top K问题：用最小堆快速找到一组数据中的前K大元素。

6. 堆的优缺点