堆

揭秘“堆”：高效的优先级队列与排序利器

1. 什么是堆？

堆是一种特殊的完全二叉树。它的主要特性是：

1. 完全二叉树： 堆必须是一棵完全二叉树。这意味着除了最后一层，其他层都被完全填满，并且最后一层的节点都尽可能地靠左排列。这种结构使得堆可以用数组来高效地表示，无需使用指针，节省了内存空间。
   • 在一个完全二叉树中，如果一个节点的索引是 i：
     • 它的左子节点的索引是 2i+1。
     • 它的右子节点的索引是 2i+2。
     • 它的父节点的索引是 (i−1)/2（整数除法）。
2. 堆序性（Heap Property）： 堆中的每个节点都满足特定的顺序关系。根据这个关系，堆可以分为两种：
   • 最大堆（Max-Heap）： 每个父节点的值都大于或等于其子节点的值。因此，根节点是整个堆中的最大值。
   • 最小堆（Min-Heap）： 每个父节点的值都小于或等于其子节点的值。因此，根节点是整个堆中的最小值。

本文后续将以最小堆为例进行讲解和实现。

为何用数组表示？

完全二叉树的这种特性使得它的节点可以紧密地存储在一个数组中，而不会有任何空隙。通过简单的数学计算，我们就能找到任何一个节点的父节点或子节点，从而避免了传统树结构中因指针操作带来的额外开销和复杂性。

2. 堆的基本操作

堆的核心操作包括：插入（Insert） 和 删除根节点（Extract Min/Max）。这两个操作都通过维护堆的“堆序性”来实现。

2.1 插入操作（Insert）

向堆中插入一个新元素时，为了保持堆的完全二叉树结构和堆序性，我们通常这样做：

1. 将新元素添加到堆的末尾（数组的最后一个位置），以保持完全二叉树的特性。
2. 然后，进行**“上浮”（Heapify-up / Sift-up / Bubble-up）** 操作：将新元素与其父节点进行比较。如果新元素比父节点小（最小堆）或大（最大堆），则交换它们的位置。这个过程重复进行，直到新元素到达正确的位置（满足堆序性）或者到达根节点。

这个上浮过程的时间复杂度是 O(logn)，因为每次比较和交换都会使元素向上移动一层。

2.2 删除根节点（Extract Min/Max）

删除堆中的根节点（例如，从最小堆中取出最小值）是另一个核心操作：

1. 取出根节点的值。
2. 为了保持完全二叉树的结构，将堆中的最后一个元素移动到根节点的位置。
3. 然后，进行**“下沉”（Heapify-down / Sift-down / Bubble-down）** 操作：将新根元素与其子节点进行比较。如果它比子节点大（最小堆）或小（最大堆），则与合适的子节点（最小堆选较小的子节点，最大堆选较大的子节点）交换位置。这个过程重复进行，直到元素到达正确的位置（满足堆序性）或者到达叶子节点。

这个下沉过程的时间复杂度也是 O(logn)，因为它每次比较和交换都会使元素向下移动一层。

---

3. C 语言实现最小堆

我们用一个数组来表示堆，并实现其核心操作。

#include <stdio.h>
#include <stdlib.h>
#include <limits.h> // for INT_MAX

#define MAX_HEAP_SIZE 100 // 定义堆的最大容量

// 最小堆结构体
typedef struct MinHeap {
    int* arr;       // 存储堆元素的数组
    int capacity;  // 堆的最大容量
    int size;      // 堆当前元素的数量
} MinHeap;

// 创建一个最小堆
MinHeap* createMinHeap(int capacity) {
    MinHeap* heap = (MinHeap*)malloc(sizeof(MinHeap));
    if (heap == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    heap->capacity = capacity;
    heap->size = 0;
    heap->arr = (int*)malloc(sizeof(int) * capacity);
    if (heap->arr == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    return heap;
}

// 获取父节点的索引
int getParentIndex(int i) {
    return (i - 1) / 2;
}

// 获取左子节点的索引
int getLeftChildIndex(int i) {
    return 2 * i + 1;
}

// 获取右子节点的索引
int getRightChildIndex(int i) {
    return 2 * i + 2;
}

// 交换两个元素
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 上浮操作：维护堆的最小堆序性
// 当一个元素被插入到堆的末尾时，需要向上调整它的位置
void heapifyUp(MinHeap* heap, int index) {
    int parentIndex = getParentIndex(index);
    // 如果当前节点不是根节点，且比父节点小
    while (index > 0 && heap->arr[parentIndex] > heap->arr[index]) {
        swap(&heap->arr[index], &heap->arr[parentIndex]);
        index = parentIndex;
        parentIndex = getParentIndex(index);
    }
}

// 下沉操作：维护堆的最小堆序性
// 当根节点被删除或元素被修改时，需要向下调整它的位置
void heapifyDown(MinHeap* heap, int index) {
    int smallest = index;
    int leftChild = getLeftChildIndex(index);
    int rightChild = getRightChildIndex(index);

    // 如果左子节点存在且比当前最小的小
    if (leftChild < heap->size && heap->arr[leftChild] < heap->arr[smallest]) {
        smallest = leftChild;
    }

    // 如果右子节点存在且比当前最小的小
    if (rightChild < heap->size && heap->arr[rightChild] < heap->arr[smallest]) {
        smallest = rightChild;
    }

    // 如果最小的不是当前节点，则交换并继续向下沉
    if (smallest != index) {
        swap(&heap->arr[index], &heap->arr[smallest]);
        heapifyDown(heap, smallest);
    }
}

// 插入元素到最小堆
void insertMinHeap(MinHeap* heap, int value) {
    if (heap->size == heap->capacity) {
        printf("堆已满，无法插入！\n");
        return;
    }
    // 将新元素添加到数组末尾
    heap->arr[heap->size] = value;
    heap->size++;
    // 进行上浮操作
    heapifyUp(heap, heap->size - 1);
    printf("插入 %d 成功。\n", value);
}

// 提取最小元素（根节点）
int extractMin(MinHeap* heap) {
    if (heap->size <= 0) {
        printf("堆为空，无法提取！\n");
        return INT_MAX; // 返回一个表示错误的值
    }
    if (heap->size == 1) { // 只有一个元素
        heap->size--;
        return heap->arr[0];
    }

    // 保存根节点的值
    int root = heap->arr[0];
    // 将最后一个元素移动到根节点
    heap->arr[0] = heap->arr[heap->size - 1];
    heap->size--;
    // 进行下沉操作
    heapifyDown(heap, 0);

    return root;
}

// 获取堆的最小元素（不删除）
int getMin(MinHeap* heap) {
    if (heap->size <= 0) {
        printf("堆为空。\n");
        return INT_MAX;
    }
    return heap->arr[0];
}

// 打印堆的数组表示
void printHeap(MinHeap* heap) {
    printf("堆的数组表示: [");
    for (int i = 0; i < heap->size; i++) {
        printf("%d", heap->arr[i]);
        if (i < heap->size - 1) {
            printf(", ");
        }
    }
    printf("]\n");
}

// 释放堆内存
void freeMinHeap(MinHeap* heap) {
    if (heap == NULL) return;
    free(heap->arr);
    free(heap);
    printf("堆内存已释放。\n");
}

int main() {
    MinHeap* myHeap = createMinHeap(MAX_HEAP_SIZE);

    printf("------ 插入元素 ------\n");
    insertMinHeap(myHeap, 3);
    printHeap(myHeap); // [3]
    insertMinHeap(myHeap, 2);
    printHeap(myHeap); // [2, 3]
    insertMinHeap(myHeap, 15);
    printHeap(myHeap); // [2, 3, 15]
    insertMinHeap(myHeap, 5);
    printHeap(myHeap); // [2, 3, 5, 15]
    insertMinHeap(myHeap, 4);
    printHeap(myHeap); // [2, 3, 4, 15, 5] (实际为[2, 3, 4, 15, 5]或[2, 5, 4, 15, 3]等，取决于具体路径，但都满足最小堆序性)
    insertMinHeap(myHeap, 45);
    printHeap(myHeap); // [2, 3, 4, 45, 5, 15]

    printf("\n------ 提取最小元素 ------\n");
    int minVal = extractMin(myHeap);
    printf("提取最小元素: %d\n", minVal); // Expected: 2
    printHeap(myHeap); // [3, 5, 4, 45, 15] (根节点变为3，并重新调整)

    minVal = extractMin(myHeap);
    printf("提取最小元素: %d\n", minVal); // Expected: 3
    printHeap(myHeap); // [4, 5, 15, 45]

    printf("\n------ 获取最小元素 ------\n");
    printf("当前最小元素 (不删除): %d\n", getMin(myHeap)); // Expected: 4

    printf("\n------ 释放内存 ------\n");
    freeMinHeap(myHeap);

    return 0;
}

---

4. 堆的应用场景

堆因其高效的插入和删除根节点操作，在许多场景下都非常有用：

• 优先级队列（Priority Queue）： 这是堆最经典的应用。当需要频繁地获取或处理最高/最低优先级的元素时（例如，操作系统的任务调度、事件模拟、图算法中的 Dijkstra 算法和 Prim 算法），堆是最佳选择。
• 堆排序（Heapsort）： 一种高效的排序算法，时间复杂度为 O(nlogn)。它通过将待排序元素构建成一个堆，然后重复提取根节点来实现排序。
• Top K 问题： 在大量数据中查找最大/最小的 K 个元素。例如，找出成绩最高的 10 个学生，或者找出流量最大的 10 个 IP 地址。可以使用大小为 K 的小顶堆或大顶堆来高效解决。
• 在线中位数查找： 结合两个堆（一个最大堆和一个最小堆）可以高效地维护数据流的中位数。
• 数据压缩（霍夫曼编码）： 霍夫曼树的构建过程就使用了优先级队列（堆）。