数据结构-堆-易微帮

堆的定义

堆是一种在内存中以数组形式高效实现的树形数据结构，具有完全二叉树的性质，并且通过堆序性质保证了可以快速访问最大或最小元素。它在各种算法和应用中发挥着关键作用，特别是在需要快速访问和动态更新数据的场景中。（完全二叉树：只允许最后一行不满，且数据向左补满）

怎么认识堆

结构上：

堆是一种特殊的完全二叉树，它有以下两种类型：

最大堆：任意节点的值都大于或等于其子节点的值。这意味着最大值总是位于堆的根节点。
最小堆：任意节点的值都小于或等于其子节点的值。这意味着最小值总是位于堆的根节点。

在几何上，堆通常被表示为一棵完全二叉树，其中每个节点都有可能拥有0个、1个或2个子节点，并且树的每层都被完全填满，除了最后一层，最后一层从左到右填充。

内存上：

在内存中，堆通常使用数组来实现，因为数组可以有效地表示完全二叉树的结构。在数组中，堆的每个元素都有一个索引，可以通过以下公式快速找到其父节点和子节点的索引：

父节点索引：parent(i) = floor(i / 2) - 1
左子节点索引：left(i) = 2i + 1
右子节点索引：right(i) = 2i + 2

其中，i 是当前节点的索引。

性质上：

堆的主要性质包括：

完全二叉树性质：堆在内存中可以高效地表示为一个数组，无需指针连接，减少了内存的使用。
堆序性质：保证了最大堆中根节点的值最大，最小堆中根节点的值最小。
快速访问：可以快速地访问堆中的最小（最小堆）或最大（最大堆）元素。

应用上：

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

排序：堆排序是一种利用堆结构的排序算法。
优先队列：堆是实现优先队列的有效数据结构，允许快速访问最高或最低优先级的元素。
图算法：如Dijkstra算法和A*搜索算法，使用堆来找到图中的最短路径。
调度：在操作系统中，进程调度可以用堆来实现，以快速选择具有最高优先级的进程。
数据压缩：如Huffman编码，使用最小堆来构建最优前缀编码树。
内存管理：在内存分配算法中，堆用于管理内存块。

堆和栈的区别：

（1）申请方式的不同。栈由系统自动分配；而堆是人为申请开辟。
（2）申请大小的不同。栈获得的空间较小；而堆获得的空间较大。
（3）申请效率的不同。栈由系统自动分配，速度较快；而堆一般速度比较慢。
（4）存储内容的不同。栈在函数调用时，函数调用语句的下一条可执行语句的地址第一个进栈，然后函数的各个参数进栈，其中静态变量是不入栈的；而堆一般是在头部用一个字节存放堆的大小，堆中的具体内容是人为安排。
（5）底层不同。栈是连续的空间；而堆是不连续的空间。

堆的应用及实现（详解）

先介绍堆的几个基本操作：（具体实现后面补充）

1.建堆

1）自顶向下

按照已经给的数组顺序将元素插入堆（末尾） + 上滤

2）自底向上

本身就先作为一个已经建好的堆（用数组表示），在此基础上用下滤操作

2.下滤

对于根节点来说，左右节点中遇到优先级更高的就交换位置（这里的优先级取决于：按照最大堆还是最小堆去下滤）

3.上滤

对于最后一个元素来说，父节点中遇到优先级更低的就交换位置（这里的优先级取决于：按照最大堆还是最小堆去上滤）【注意循环结束条件：直到index == 0时，当前节点遍历到了堆顶，退出】

// 上滤操作，确保堆从新插入的节点开始满足最大堆性质
void percolateUp(int heap[], int size, int index) {
    while (index > 0 && heap[index] > heap[(index - 1) / 2]) {
        // 交换当前节点和它的父节点
        swap(&heap[index], &heap[(index - 1) / 2]);
        // 移动到父节点位置继续比较
        index = (index - 1) / 2;
    }
}

4.堆的插入

插入到堆的末尾 + 上滤（建堆的思路）

// 插入新元素到堆中
void heapInsert(int heap[], int *size, int value) {
    // 将新元素添加到堆的末尾（数组中的下一个空闲位置）
    heap[(*size) - 1] = value;
    // 对新添加的元素进行上滤
    percolateUp(heap, *size, (*size) - 1);
    // 增加堆的大小
    (*size)++;
}

【注意：其中数组的大小并不是size那么大，由于C语言中数组的大小在声明编译时就已经确定，所以提前就准备一个较大的数组】

5.堆的删除

删除堆顶元素（根节点）：交换根节点和最后一个节点的值，然后直接对堆的size-- + 下滤（主要部分）

// 删除最大堆中的根节点（即最大元素），并重新调整堆结构
void removeMax(int heap[], int *size) {
    if (*size <= 0) {
        return; // 堆为空，无需删除
    }

    // 将根节点与最后一个节点交换
    swap(&heap[0], &heap[(*size) - 1]);

    // 从堆中移除最后一个节点（即最大值）
    (*size)--;

    // 对调整后的堆进行下滤，以保持最大堆性质
    maxHeapify(heap, *size, 0);
}

堆排序

算法思想

删除并返回堆顶元素 + 把末尾元素放到根节点位置 + 下滤，操作反复进行。

具体实现及注释

#include <stdio.h>

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

// 构建最大堆
void buildMaxHeap(int heap[], int size) {
    // 从最后一个非叶子节点开始，向上进行堆化
    for (int i = size / 2 - 1; i >= 0; i--) {
        maxHeapify(heap, size, i);
    }
}

// 下滤操作，确保堆从指定节点开始满足最大堆性质
void maxHeapify(int heap[], int size, int i) {
    int left = 2 * i + 1;    // 左子节点索引
    int right = 2 * i + 2;   // 右子节点索引
    int largest = i;         // 最初假设当前节点是最大值节点

    // 检查左子节点，如果存在并且值更大，则更新最大值节点
    if (left < size && heap[left] > heap[largest]) {
        largest = left;
    }

    // 检查右子节点，如果存在并且值更大，则更新最大值节点
    if (right < size && heap[right] > heap[largest]) {
        largest = right;
    }

    // 如果找到的最大子节点不等于当前节点，交换他们，并递归地对最大子节点进行堆化
    if (largest != i) {
        swap(&heap[i], &heap[largest]);
        maxHeapify(heap, size, largest); // 递归地对最大子节点进行堆化
    }
}

// 执行堆排序
void heapSort(int heap[], int size) {
    // 首先构建最大堆
    buildMaxHeap(heap, size);

    // 将堆顶元素（最大元素）与最后一个元素交换，然后缩小堆的大小并重新堆化
    for (int i = size - 1; i > 0; i--) {
        swap(&heap[0], &heap[i]); // 交换堆顶元素和最后一个元素
        maxHeapify(heap, i, 0);   // 重新堆化剩下的子堆
    }
}

// 打印数组
void printArray(int array[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
}

int main() {
    int data[] = {12, 11, 13, 5, 6, 7};
    int size = sizeof(data) / sizeof(data[0]);

    // 执行堆排序
    heapSort(data, size);

    // 打印排序后的数组
    printf("Sorted array: \n");
    printArray(data, size);

    return 0;
}

其中，函数介绍：

swap 函数用于交换数组中的两个元素。
buildMaxHeap 函数用于从数组构建最大堆。
maxHeapify 函数用于确保从给定索引 i 开始的子树满足最大堆的性质。这是通过递归调用 maxHeapify 来完成的，直到子树满足最大堆的性质。
heapSort 函数首先调用 buildMaxHeap 来构建最大堆，然后通过交换堆顶元素和当前未排序部分的最后一个元素，并逐步缩小未排序部分的大小，调用 maxHeapify 来重新堆化剩余的子堆，直到整个数组变为有序。

核心的代码：

  // 将堆顶元素（最大元素）与最后一个元素交换，然后缩小堆的大小并重新堆化
    for (int i = size - 1; i > 0; i--) {
        swap(&heap[0], &heap[i]); // 交换堆顶元素和最后一个元素
        maxHeapify(heap, i, 0);   // 重新堆化剩下的子堆
    }

数据结构-堆