数据结构-堆排序

1.定义
 
-堆中每个节点的值都必须大于等于（或小于等于）其左右子节点的值。如果每个节点的值都大于等于其子节点的值，这样的堆称为大根堆（大顶堆）；如果每个节点的值都小于等于其子节点的值，称为小根堆（小顶堆）。

2.堆的性质：
堆中某个节点的值总是不大于或不小于其父节点的值；

堆总是一棵完全二叉树；

3.堆的实现

3.1堆向下调整算法
现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整

heap.h文件
// 确保头文件只被编译一次，避免重复包含导致的编译错误
#pragma once
// 包含标准库头文件，用于内存分配和动态内存管理，如 malloc、realloc、free 等函数
#include <stdlib.h>
// 包含断言库头文件，用于调试时检查条件是否为真，如果条件为假则程序终止
#include <assert.h>
// 包含布尔类型定义的头文件，使得代码可以使用 bool 类型
#include <stdbool.h>
// 包含标准输入输出库头文件，提供了基本的输入输出功能，如 printf、scanf 等
#include <stdio.h>// 定义堆中数据的类型，这里将 int 类型重命名为 HPDataType，方便后续修改堆中数据的类型
typedef int HPDataType;// 定义堆的结构体
typedef struct Heap
{// 指向堆数据数组的指针，用于存储堆中的元素HPDataType* a;// 堆中当前元素的数量int size;// 堆数组的容量，即当前分配的内存可以存储的元素个数int capacity;
} HP;// 堆操作接口函数声明// 初始化堆
// 参数：php 是指向堆结构体的指针，用于初始化堆的各项属性
void HeapInit(HP* php);// 销毁堆
// 参数：php 是指向堆结构体的指针，用于释放堆所占用的内存资源
void HeapDestroy(HP* php);// 向堆中插入一个元素
// 参数：php 是指向堆结构体的指针，x 是要插入的元素
void HeapPush(HP* php, HPDataType x);// 删除堆顶元素
// 参数：php 是指向堆结构体的指针，该操作会移除堆中优先级最高的元素
void HeapPop(HP* php);     // 获取堆顶元素
// 参数：php 是指向堆结构体的指针，返回堆顶元素的值
HPDataType HeapTop(HP* php);// 判断堆是否为空
// 参数：php 是指向堆结构体的指针，返回一个布尔值，表示堆是否为空
bool HeapEmpty(HP* php);// 获取堆中元素的数量
// 参数：php 是指向堆结构体的指针，返回堆中当前元素的个数
int HeapSize(HP* php);

插入元素（向上调整适合逐个插入元素构建小堆，向下调整适合对已有数据构建小堆且效率更高）

void HeapPush(HP* php, HPDataType x) 
{assert(php);// 扩容检查if (php->size == php->capacity) {int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, newCapacity * sizeof(HPDataType));if (tmp == NULL) {perror("realloc fail");exit(EXIT_FAILURE);  // 内存不足直接退出}php->a = tmp;php->capacity = newCapacity;}// 插入并调整php->a[php->size++] = x;AdjustUp(php->a, php->size - 1);
}

向上调整算法：

static void AdjustUp(HPDataType* a, int child) 
{int parent = (child - 1) / 2;while (child > 0) {  // 小堆逻辑if (a[child] < a[parent]) {Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else {break;}}
}

向下调整算法：

static void AdjustDown(HPDataType* a, int n, int parent) 
{int child = parent * 2 + 1;while (child < n) {// 选择较小的子节点（小堆）if (child + 1 < n && a[child + 1] < a[child]) {child++;}if (a[child] < a[parent]) {Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else {break;}}
}

4.建堆时间复杂度

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：

因此：建堆的时间复杂度为O(N)。

5.堆的插入

先插入一个10到数组的尾上，再进行向上调整算法，直到满足堆。

6.堆的删除

删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。

7.堆实现

heap.h文件
#pragma once
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <stdio.h>typedef int HPDataType;typedef struct Heap
{HPDataType* a;int size;int capacity;
} HP;// 堆操作接口
void HeapInit(HP* php);
void HeapDestroy(HP* php);
void HeapPush(HP* php, HPDataType x);
void HeapPop(HP* php);      // 删除堆顶
HPDataType HeapTop(HP* php);
bool HeapEmpty(HP* php);
int HeapSize(HP* php);heap.c文件#define _CRT_SECURE_NO_WARNINGS
#include "Heap.h"// 静态辅助函数（仅本文件可见）
static void Swap(HPDataType* p1, HPDataType* p2) 
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}static void AdjustUp(HPDataType* a, int child) 
{int parent = (child - 1) / 2;while (child > 0) {  // 小堆逻辑if (a[child] < a[parent]) {Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else {break;}}
}static void AdjustDown(HPDataType* a, int n, int parent) 
{int child = parent * 2 + 1;while (child < n) {// 选择较小的子节点（小堆）if (child + 1 < n && a[child + 1] < a[child]) {child++;}if (a[child] < a[parent]) {Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else {break;}}
}// 初始化堆
void HeapInit(HP* php) 
{assert(php);php->a = NULL;php->size = php->capacity = 0;
}// 销毁堆
void HeapDestroy(HP* php) 
{assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;
}// 插入元素
void HeapPush(HP* php, HPDataType x) 
{assert(php);// 扩容检查if (php->size == php->capacity) {int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, newCapacity * sizeof(HPDataType));if (tmp == NULL) {perror("realloc fail");exit(EXIT_FAILURE);  // 内存不足直接退出}php->a = tmp;php->capacity = newCapacity;}// 插入并调整php->a[php->size++] = x;AdjustUp(php->a, php->size - 1);
}// 删除堆顶
void HeapPop(HP* php) 
{assert(php && !HeapEmpty(php));Swap(&php->a[0], &php->a[--php->size]);AdjustDown(php->a, php->size, 0);
}// 获取堆顶元素
HPDataType HeapTop(HP* php)
{assert(php && !HeapEmpty(php));return php->a[0];
}// 判断堆是否为空
bool HeapEmpty(HP* php) 
{assert(php);return php->size == 0;
}// 获取堆大小
int HeapSize(HP* php) 
{assert(php);return php->size;
}main.c  测试文件
int main()
{HP hp;HeapInit(&hp);int a[] = { 12, 34, 56, 70, 45, 67, 13, 35, 43, 67, 89, 90, 112, 113, 456 };for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++){HeapPush(&hp, a[i]);}// 小堆特性会从小到大弹出while (!HeapEmpty(&hp)){printf("%d ", HeapTop(&hp));HeapPop(&hp);}return 0;
}

8.堆的应用

 -堆排序
堆排序即利用堆的思想来进行排序，总共分为两个步骤：
1. 建堆
升序：建大堆
降序：建小堆
2. 利用堆删除思想来进行排序
建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

9.TopK问题

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：
1. 用数据集合中前K个元素来建堆
前k个最大的元素，则建小堆
前k个最小的元素，则建大堆
2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
#include <stdbool.h>  // 定义堆中数据的类型，这里使用 int 类型
typedef int HPDataType;// 定义堆的结构体
typedef struct Heap
{HPDataType* a;  // 指向堆数据的指针int size;       // 当前堆中元素的数量int capacity;   // 堆的容量
} HP;// 初始化堆
void HeapInit(HP* php) 
{// 断言传入的堆指针不为空assert(php);// 初始化堆数据指针为空php->a = NULL;// 初始化堆中元素数量为 0php->size = 0;// 初始化堆的容量为 0php->capacity = 0;
}// 销毁堆，释放堆所占用的内存
void HeapDestroy(HP* php) 
{// 断言传入的堆指针不为空assert(php);// 释放堆数据所占用的内存free(php->a);// 将堆数据指针置为空php->a = NULL;// 将堆的容量和元素数量都置为 0php->capacity = php->size = 0;
}// 交换两个元素的值
void Swap(HPDataType* p1, HPDataType* p2) 
{// 临时变量，用于存储其中一个元素的值HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}// 向上调整堆，保持堆的性质
void AdjustUp(HPDataType* a, int child) 
{// 计算父节点的索引int parent = (child - 1) / 2;// 当子节点的索引大于 0 时，继续调整while (child > 0) {// 如果子节点的值小于父节点的值if (a[child] < a[parent]) {// 交换子节点和父节点的值Swap(&a[child], &a[parent]);// 更新子节点为原来的父节点child = parent;// 重新计算新的父节点的索引parent = (child - 1) / 2;}else {// 如果子节点的值不小于父节点的值，停止调整break;}}
}// 向下调整堆，保持堆的性质
void AdjustDown(int* a, int n, int parent) 
{// 计算左子节点的索引int child = parent * 2 + 1;// 当子节点的索引小于堆中元素的数量时，继续调整while (child < n) {// 如果右子节点存在且右子节点的值小于左子节点的值if (child + 1 < n && a[child + 1] < a[child]) {// 更新子节点为右子节点++child;}// 如果子节点的值小于父节点的值if (a[child] < a[parent]) {// 交换父节点和子节点的值Swap(&a[parent], &a[child]);// 更新父节点为原来的子节点parent = child;// 重新计算新的子节点的索引child = parent * 2 + 1;}else {// 如果子节点的值不小于父节点的值，停止调整break;}}
}// 向堆中插入一个元素
void HeapPush(HP* php, HPDataType x) 
{// 断言传入的堆指针不为空assert(php);// 如果堆的元素数量等于堆的容量，需要扩容if (php->size == php->capacity) {// 计算新的容量int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;// 重新分配内存HPDataType* tmp = (HPDataType*)realloc(php->a, newCapacity * sizeof(HPDataType));// 如果内存分配失败if (tmp == NULL) {// 输出错误信息perror("realloc fail");return;}// 更新堆数据指针php->a = tmp;// 更新堆的容量php->capacity = newCapacity;}// 将新元素插入到堆的末尾php->a[php->size++] = x;// 向上调整堆AdjustUp(php->a, php->size - 1);
}// 判断堆是否为空
bool HeapEmpty(HP* php) 
{// 如果堆中元素数量为 0，则堆为空return php->size == 0;
}// 获取堆中元素的数量
int HeapSize(HP* php) 
{return php->size;
}// 删除堆顶元素
void HeapPop(HP* php) 
{// 断言传入的堆指针不为空且堆不为空assert(php && !HeapEmpty(php));// 交换堆顶元素和堆的最后一个元素Swap(&php->a[0], &php->a[php->size - 1]);// 堆的元素数量减 1php->size--;// 向下调整堆AdjustDown(php->a, php->size, 0);
}// 获取堆顶元素
HPDataType HeapTop(HP* php) 
{// 断言传入的堆指针不为空且堆不为空assert(php && !HeapEmpty(php));return php->a[0];
}// 生成随机数据并保存到文件中
void CreateNate()
{// 生成 1000 个随机数int n = 1000;// 初始化随机数种子srand(time(0));// 定义要保存数据的文件名const char* file = "data.txt";// 以写入模式打开文件FILE* fin = fopen(file, "w");// 如果文件打开失败if (fin == NULL) {// 输出错误信息perror("fopen error");return;}// 循环生成随机数并写入文件for (int i = 0; i < n; i++) {// 生成 0 到 9999 之间的随机数int x = rand() % 10000;// 将随机数写入文件fprintf(fin, "%d\n", x);}// 关闭文件fclose(fin);
}// 打印文件中最大的 k 个元素
void PrintTopK(int k) 
{// 定义要读取数据的文件名const char* file = "data.txt";// 以读取模式打开文件FILE* fin = fopen(file, "r");// 如果文件打开失败if (fin == NULL) {// 输出错误信息perror("fopen error");return;}// 分配内存，用于存储最小堆int* kminheap = (int*)malloc(sizeof(int) * k);// 如果内存分配失败if (kminheap == NULL){// 输出错误信息perror("malloc fail");return;}// 从文件中读取前 k 个元素到最小堆中for (int i = 0; i < k; i++) {fscanf(fin, "%d", &kminheap[i]);}// 对最小堆进行建堆操作for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(kminheap, k, i);}// 用于存储从文件中读取的元素int val = 0;// 从文件中继续读取元素while (fscanf(fin, "%d", &val) != EOF) {// 如果读取的元素大于最小堆的堆顶元素if (val > kminheap[0]) {// 替换堆顶元素kminheap[0] = val;// 向下调整堆AdjustDown(kminheap, k, 0);}}// 打印最小堆中的元素for (int i = 0; i < k; i++) {printf("%d ", kminheap[i]);}printf("\n");// 释放最小堆所占用的内存free(kminheap);// 关闭文件fclose(fin);
}int main() 
{// 生成随机数据并保存到文件中CreateNate();// 打印文件中最大的 3 个元素PrintTopK(3);return 0;
}