堆的建立、插入、出堆、堆化、topk问题、堆排序(C语言实现)

2024-09-03 01:12

本文主要是介绍堆的建立、插入、出堆、堆化、topk问题、堆排序(C语言实现),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

堆的建立、插入、出堆、堆化、topk问题、堆排序

  • 使用数组来存储堆
    • 堆顶为序号0,堆底为序号 size - 1
  • 假设树为完全二叉树,当前节点和双亲节点的关系可以通过公式表达
// 小顶堆: 对 heaptifyUp 和 heaptifyDown 函数的逻辑进行一些调整。
void initHeap(float **arr, int *size) { *arr = (float *)malloc(sizeof(float) * MAX_SIZE); *size = 0; }
void peekTop(float *arr, int size, float *x) { if (size <= 0) return; *x = arr[0]; }
void getParent(int i, int *p_idx) { *p_idx = (i - 1) / 2; }
void getLeftChild(int i, int *lc_idx) { *lc_idx = 2 * i + 1; }
void getRightChild(int i, int *rc_idx) { *rc_idx = 2 * i + 2; }
void heaptifyUp(float *arr, int idx) { // 比较当前节点与其父节点的大小。如果当前节点的值小于父节点的值,则交换它们,并继续向上调整。int cur = idx;while (cur > 0) {  // 只要 cur 不是根节点int par; getParent(cur, &par); if (arr[cur] >= arr[par]) break; // 如果当前节点大于等于父节点,退出循环float tmp = arr[cur]; arr[cur] = arr[par]; arr[par] = tmp; cur = par;  // 交换当前节点和父节点, 更新 cur 为父节点索引}
}
void heaptifyDown(float *arr, int size, int idx) { // 比较当前节点与其左右子节点的大小。选择最小的子节点,如果当前节点大于这个子节点,则交换它们,并继续向下调整。int cur = idx;while (true) {int lc, rc, minidx = cur; getLeftChild(cur, &lc); getRightChild(cur, &rc);if (lc < size && arr[lc] < arr[minidx]) { minidx = lc; } // 找到当前节点和左子节点中的最小值if (rc < size && arr[rc] < arr[minidx]) { minidx = rc; } // 找到当前节点和右子节点中的最小值if (minidx == cur) break; // 如果当前节点是最小值,退出循环float tmp = arr[cur]; arr[cur] = arr[minidx]; arr[minidx] = tmp; cur = minidx;  // 交换当前节点和最小值节点, 更新 cur 为新的索引}
}
void pushHeap(float *arr, int *size, float x) {if ((*size) >= MAX_SIZE) return; // 如果堆已满,直接返回arr[*size] = x; (*size)++; // 将新元素放在堆的最后一个位置heaptifyUp(arr, (*size) - 1); // 重新调整堆
}
void popHeap(float *arr, int *size, float *val) {if ((*size) <= 0) return; // 如果堆为空,直接返回*val = arr[0]; arr[0] = arr[(*size) - 1]; // 将堆的最后一个元素放在堆顶(*size)--; heaptifyDown(arr, *size, 0); // 重新调整堆
}
void buildHeap(float *arr, int size){// 使用heaptifyDown的原因是,如果使用 heaptifyUp从树的底部向上调整,每个节点在最坏情况下可能需要一直移到树的根部(并且底部的节点数量多)。// 这意味着可能需要执行更多的比较和交换操作。而如果我们从上往下调整,每个节点最多只需要向下移动几层(通常是树的高度),这使得整体效率非常高。for (int i = size / 2 - 1; i >= 0; i--) heaptifyDown(arr, size, i); // 从最后一个非叶子节点(size/2 - 1)开始,向上调整堆;
}
void freeHeap(float **arr) { if (*arr) { free(*arr); *arr = NULL; } }
void top_k(float *arr, int size, float *res, int k) {if (k <= 0 || k > size) return;float *heap = (float *)malloc(sizeof(float) * k); int heap_size = 0;for (int i = 0; i < k; i++){ pushHeap(heap, &heap_size, arr[i]); } //  // 初始化堆,放入前 k 个元素for (int i = k; i < size; i++){ if (arr[i] > heap[0]) { float tmp; popHeap(heap, &heap_size, &tmp); pushHeap(heap, &heap_size, arr[i]); } } // 处理剩余的元素for (int i = 0; i < k; i++) { popHeap(heap, &heap_size, &res[k - 1 - i]); } // 将堆中的元素按降序输出到 res 数组freeHeap(&heap);
}
// parallel: 在构建堆时,并行化处理多个子树的下沉操作
void heap_sort(float *heap, int size){ // 堆排序,从大道小排序buildHeap( heap, size); // 构建小顶堆while (size > 1) {float tmp = heap[0]; heap[0] = heap[size - 1]; heap[size - 1] = tmp; size--; // 将堆顶元素与堆的最后一个元素交换,每次循环最小的元素被调整到末尾,堆的大小减1heaptifyDown(heap, size, 0); // 从堆顶开始重新调整堆}freeHeap(&heap);
} 大顶堆
//void initHeap(float **arr, int *size) { *arr = (float *)malloc(sizeof(float) * MAX_SIZE); *size = 0; } // 初始化堆的大小为0
//void peekTop(float *arr, int size, float *x) { if (size <= 0) return ; *x = arr[0]; }
//void getParent(int i, int *p_idx) { *p_idx = (i - 1) / 2; }
//void getLeftChild(int i, int *lc_idx) { *lc_idx = 2 * i + 1; }
//void getRightChild(int i, int *rc_idx) { *rc_idx = 2 * i + 2; }
//void heaptifyUp(float *arr, int idx){
//    int cur = idx;
//    while (cur > 0){  // 只要 cur 不是根节点
//        int par; getParent(cur, &par); if (arr[cur] < arr[par]) break; // 如果当前节点小于父节点,退出循环
//        float tmp = arr[cur]; arr[cur] = arr[par]; arr[par] = tmp; cur = par;  // 交换当前节点和父节点
//    }
//}
//void heaptifyDown(float *arr, int size, int idx){
//    int cur = idx;
//    while (true){
//        int lc, rc, maxidx = cur; getLeftChild(cur, &lc); getRightChild(cur, &rc);
//        if (lc < size && arr[lc] > arr[maxidx]) { maxidx = lc;} // 找到当前节点和左子节点中的最大值
//        if (rc < size && arr[rc] > arr[maxidx]) { maxidx = rc;} // 找到当前节点和右子节点中的最大值
//        if (maxidx == cur) break; // 如果当前节点是最大值,退出循环
//        float tmp = arr[cur]; arr[cur] = arr[maxidx]; arr[maxidx] = tmp; cur = maxidx; // 交换当前节点和最大值节点
//    }
//}
//void pushHeap(float *arr, int *size, float x){
//    if ((*size) >= MAX_SIZE) return; // 如果堆已满,直接返回
//    arr[*size] = x; (*size)++; // 将新元素放在堆的最后一个位置
//    heaptifyUp(arr, (*size) - 1); // 重新调整堆
//}
//void popHeap(float *arr, int *size, float *val){
//    if ((*size) <= 0) return; // 如果堆为空,直接返回
//    *val = arr[0];
//    arr[0] = arr[(*size) - 1]; // 将堆的最后一个元素放在堆顶
//    (*size)--;
//    heaptifyDown(arr, *size,0); // 重新调整堆
//}
//void freeHeap(float **arr) { if (*arr) { free(*arr); *arr = NULL; } }

这篇关于堆的建立、插入、出堆、堆化、topk问题、堆排序(C语言实现)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1131599

相关文章

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现,因为rasa本身是带有remindschedule模块的。不过经过一番折腾后,忽然发现,chatbot上实现的定时,语音助手不一定会有响应。因为,我目前语音助手的代码设置了长时间无应答会结束对话,这样一来,chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢? 我最后选择的方法是用threading.Time

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸(两张壁纸可不一致)

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸: 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  (注意不能是bmp格式) 替换默认锁屏壁纸: 将图片资源放入vendo

C#实战|大乐透选号器[6]:实现实时显示已选择的红蓝球数量

哈喽,你好啊,我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记,这是第6篇; 接下来实现实时显示当前选中红球数量,蓝球数量; 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时,在对应的位置显示实时已选择的红球、蓝球的数量; 02 标签名称 分别设置Label标签名称为:lblRedCount、lblBlueCount

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时,您应该注意以下几个关键点: 平衡精度 平衡精度是衡量平衡机性能的核心指标,直接影响到不平衡量的检测与校准的准确性,从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声,提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮,适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监

科研绘图系列:R语言扩展物种堆积图(Extended Stacked Barplot)

介绍 R语言的扩展物种堆积图是一种数据可视化工具,它不仅展示了物种的堆积结果,还整合了不同样本分组之间的差异性分析结果。这种图形表示方法能够直观地比较不同物种在各个分组中的显著性差异,为研究者提供了一种有效的数据解读方式。 加载R包 knitr::opts_chunk$set(warning = F, message = F)library(tidyverse)library(phyl

透彻!驯服大型语言模型(LLMs)的五种方法,及具体方法选择思路

引言 随着时间的发展,大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用,随着人们期望的不断增加,目标也发生了巨大的变化。在短短的几个月的时间里,人们对大模型的认识已经从对其zero-shot能力感到惊讶,转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构(例如Transformer)对海量的、多种多样的数据分布进行建模得到,它包含了大量的先验