当前位置： 首页 > news >正文

数据结构-堆排序

news 2025/5/9 13:07:32

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;
}

http://www.xdnf.cn/news/349525.html

相关文章：

  • Houdini 深圳实操交流会！即将开幕
  • 代码随想录第39天：单调栈
  • VBA经典应用69例应用8：利用VBA，完成自动运行任务的预设
  • xiaopiu原型设计工具笔记
  • Windows 环境变量完全指南：系统变量、用户变量与 PATH 详解
  • 在不同环境下部署和运行基于后量子密码的轻量级通信协议的详细指南
  • pm2如何执行脚本批量启动多个服务
  • 认识守卫-以及简单的示例和装饰器
  • Java网络编程：理解URI、URL和URN
  • python线上学习进度报告
  • Android13 权限管理机制整理
  • 308.旅行终点站
  • 正点原子IMX6U开发板移植Qt时出现乱码
  • 什么是死信队列？死信队列是如何导致的？
  • TLS 1.3：一把打不开旧锁的新钥匙，为何难成主流？
  • Blind SSRF with Shellshock exploitation过关
  • [人机交互]以用户为中心的交互设计
  • 基于译码器和锁存器的运行逻辑的简易算法
  • 算法解密：轮转数组问题全解析
  • 多源地震资料处理中的震源信号分离算法资料
  • Java内存分配
  • 【git】git fsmonitor
  • 第四章：基于langchain构造一个完整RAG系统
  • 移动端返回指定页面
  • 本地聊天机器人部署方案
  • 《运维那些事儿》专栏总目录(持续更新)
  • SQLite3介绍与常用语句汇总
  • 【日撸 Java 三百行】Day 5（Switch语句）
  • SOA 与微服务架构深度比较
  • 【C语言】(8)—指针2