堆(两种建堆方法)、堆排序和Top-K问题

这篇具有很好参考价值的文章主要介绍了堆(两种建堆方法)、堆排序和Top-K问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


是一种完全二叉树,分为大堆,小堆

如果有一个关键码的集合 int K[ ] = {27,15,19,18,28,34,65,49,25,37} ; 把它的所有元素按完全二叉树的顺序存储方式存储
在一个一维数组中,并满足:Ki <=K2*i+1 且Ki <=K2*i+2 ( Ki >=K2*i+1 且Ki >=K2*i+2) i = 0,1,
2…,则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。

堆的性质:

  • 堆中某个节点的值总是不大于或不小于其父节点的值;
  • 堆总是一棵完全二叉树。

堆(两种建堆方法)、堆排序和Top-K问题

建堆的方式

有两种,1.向上建堆,2.向下建堆

向上建堆

时间复杂度为:O(N*logN)

typedef int HPDataType;
//交换函数
void Swap(HPDataType* a, HPDataType* b) {
	HPDataType temp = *a;
	*a = *b;
	*b = temp;
}
//向上调整的条件是:调整的child结点之前的结点应该也为大堆/小堆,所以,向上调整建堆的时候,是从数组的第一个元素开始
void ADjustUp(HPDataType* a, int child) {
	//向上调整
	int parent = (child - 1)/2;
	while (child >0) //child!=0
	{
		if (a[child] > a[parent]) 
		{
			Swap(&a[child], &a[parent]);//取地址进行交换
			//进行交换
			child = parent;
			parent = (child - 1) /2;
		}
		else {
			break;
		}
		
	}
}
//向上建堆
//for (int i = 0; i < n; i++) {
//	ADjustUp(arr, i);
//}
int main(){
    int arr[]={23,23,1,32,12,3,12,31,324};
    int n=sizeof(arr)/sizeof(arr[0]);//得到数组的个数大小
    //n-1表示为数组最后一个元素的下标,(n-1-1)/2得到其父节点,从父结点开始,向下调整
	for (int i = 0; i < n; i++) {
		ADjustUp(arr, i);
    }
}

向下建堆

时间复杂堆为:O(N)

typedef int HPDataType;
//交换函数
void Swap(HPDataType* a, HPDataType* b) {
	HPDataType temp = *a;
	*a = *b;
	*b = temp;
}
//向下调整建堆的条件为:左右子树都为大堆/小堆,所以从最后一个结点开始,又因为如果是叶子结点的话,本身调整是没有意义的,所以就从倒数第二层开始
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;
		}
	}
}
//向下建堆
int main(){
    int arr[]={23,23,1,32,12,3,12,31,324};
    int n=sizeof(arr)/sizeof(arr[0]);//得到数组的个数大小
    //n-1表示为数组最后一个元素的下标,(n-1-1)/2得到其父节点,从父结点开始,向下调整
 	for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
		AdjustDown(arr, n, i);
	}   
}

计算两种方式的时间复杂度

我们可以看到的是向下调整建堆时间复杂度更小,我们通过每一层的每一个结点的最多需要调整的次数为依据,假设高度为h,如果是向上调整的话,最后一个结点(最后一层,也就是2^(h-1)个结点),最多调整h-1次,向上的时候需要调整的每一层结点变少,层数变少,所以最后肯定是总调整次数更多

如图所示:这个图可以从数学的角度上来解决这个问题

堆(两种建堆方法)、堆排序和Top-K问题

堆排序

采用向上或者是向下调整的方法,最后实现排序,最后的时间复杂度为:O(N*logN)

//所以不管是向上还是向下建堆,时间复杂度都是为O(N*logN)
void HeapSort(int arr[],int n){
    //比较偏向于向下调整建堆 时间复杂度:O(N)
    for(int i=(n-1-1)/2;i>=0;i--){
        AdjustDown(arr,n,i);
    }
    //向上建堆,时间复杂度为 O(N*logN)
    //for (int i = 0; i < n; i++) {
	//	ADjustUp(arr, i);
	//}
    //进行排序,如果想要升序,那就建大堆,然后进行向下调整
    int end = n - 1;//从最后一个结点开始
	while (end>0) {
		Swap(&arr[end], &arr[0]);
		AdjustDown(arr, end, 0);//向下调整
		end--;
	}
	for (int i = 0; i < n; i++) {
		printf("%d ", arr[i]);
	}
}
int main()
{
    int arr[]={2,231,2,3,12,312,3,123,423,4,2};
    int n=sizeof(arr)/sizeof(arr[0]);
    HeapSort(arr,n);
    return0;
}

Top-K问题

Top-K问题:从N个数据中找出前k个最大/最小的数

当然,在N的数值不是很大的时候,我们可以使用堆排序的方法,找到对应的前k个数值,但是当N的个数为10亿,或者是100亿的时候,这个数据的处理量就不能用原本的简单的堆排序方法啦

思路如下

假如说是100亿个数据量,我们由以下的内存换算可知,100亿个整数的数据量就是将近40G,所以不能单纯用简单的堆排序来运算

新的思路如下:

  • 建立一个大小为k的数组,将前k个数值建成一个小堆
  • 最后遍历剩余的数值,对于每一个数值,都进行向下调整(如果是这个数值大于顶部结点,就代替他,并进行向下调整)
  • 最后这个小堆的数据就是最大的前k个
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]) {
            int temp = a[child];
            a[child] = a[parent];
            a[parent] = temp;
            parent = child;
            child = parent * 2 + 1;
        }
        else {
            break;
        }
    }
}
void PrintTopK(const char*file,int k){
    //输出前k个数值
    //1.我们先创建为k个数据的小堆
    int*topK=(int*)malloc(sizeof(int)*k);
    assert(topK);
    FILE*fout=fopen(file,"r");//读取文件 file
    if(fout==NULL){
        perror("open fail");
        return;
    }
    
    //读取前k个数值做小堆
    for(int i=0;i<k;i++){
        fscanf(fout,"%d",&topK[i]);//读取前k个数值在数组topK中
    }
    for(int i=(k-2)/2;i>=0;i--){
        AdjustDown(topK,k,i);//将topK数组建立小堆
    }
    
    //2.将剩余的n-k个元素依次于对顶元素进行交换,不满则替换
    int val=0;
    int ret=fscanf(fout,"%d",&val);
    while(ret!=EOF){//如果文件中的数值全部被读取,那么就会返回EOF
        if(val>topK[0]){
            topK[0]=val;//直接赋值即可,不必要交换
            AdjustDown(topK,k,0);//向下调整
        }
        ret=fscanf(fout,"%d",&val);
    }
    for(int i=0;i<k;i++){
        printf("%d",topK[i]);//打印topK数组中k个数值,这就是文件中n个数值中最大的前k个数
    }
    print("\n");
    free(topK);
    fclose(fout);
}
void CreateNData(){
    //创建N个数据
    int n=1000000;
    srand(time(0));//使用随机数前要i使用这个代码
    const char*file="data.txt";
    FILE*fin=fopen(file,"w");
    if(fin==NULL){
        perror("fopen fail");
        return;
    }
    
    for(int i=0;i<n;i++){
        int x=rand()%10000;
        fprintf(fin,"%d\n",x);//读写n个数据在fin所对应的“data.txt”文件中
    }
    fclose(fin);//关闭文件,这样才能正确的在硬盘文件中“data.txt”存储数值
}
int main()
{
    CreateNData();
    PrintTopK("data.txt",10);//表示从文件data.txt中读取前10个最大的数值
    return 0;
}

实验结果如下:成功读取出来1000000随机数中前k个最大的数字

堆(两种建堆方法)、堆排序和Top-K问题

本文主要是对于堆的定义,堆的两种创建方式,向上建堆和向下建堆,进行代码演示,并对其分析时间复杂度,且实现了堆排序,实际上堆排序就是先建立堆(向上向下都可,建议向下),然后使用while循环,循环n-1次对于头尾进行交换,然后进行向下调整,上文有详解,最后是对于Top-K堆问题的解释,并附上代码进行演示文章来源地址https://www.toymoban.com/news/detail-407961.html

到了这里,关于堆(两种建堆方法)、堆排序和Top-K问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】堆的实现,堆排序以及TOP-K问题

    目录 1.堆的概念及结构 2.堆的实现 2.1初始化堆 2.2销毁堆 2.3取堆顶元素 2.4返回堆的大小 2.5判断是否为空 2.6打印堆 2.7插入元素 2.8堆的向上调整 2.9弹出元素 2.10堆的向下调整 3. 建堆时间复杂度 4. 堆的应用 4.1 堆排序 4.2 TOP-K问题 堆是一种数据结构,它是由一组元素组成的,并

    2024年02月12日
    浏览(52)
  • 【数据结构】---堆排序+TOP-K问题(了解游戏排行底层原理)

    👧个人主页:@小沈熬夜秃头中୧⍤⃝❅ 😚小编介绍:欢迎来到我的乱七八糟小星球🌝 📋专栏:数据结构 🔑本章内容:堆排序+TOP-K问题 送给各位💌:日落跌入昭昭星野 人间忽晚 山河以秋 记得 评论📝 +点赞👍 +收藏😽 +关注💞哦~ 提示:以下是本篇文章正文内容,下面

    2024年02月06日
    浏览(48)
  • 数据结构之堆排序以及Top-k问题详细解析

    个人主页:点我进入主页 专栏分类:C语言初阶      C语言程序设计————KTV       C语言小游戏     C语言进阶 C语言刷题       数据结构初阶 欢迎大家点赞,评论,收藏。 一起努力 目录 1.前言 2.堆排序 2.1降序排序 2.2时间复杂度 3.Top-k问题 4.总结         在上一篇文

    2024年02月05日
    浏览(43)
  • 【数据结构】堆(Heap):堆的实现、堆排序、TOP-K问题

    目录 堆的概念及结构 ​编辑 堆的实现  实现堆的接口 堆的初始化 堆的打印 堆的销毁 获取最顶的根数据  交换 堆的插入(插入最后) 向上调整(这次用的是小堆) 堆的删除(删除根) 向下调整(这次用的小堆) 堆排序 TOP-K问题 如果有一个关键码的集合 K = { , , , …

    2024年02月05日
    浏览(54)
  • 数据结构-堆的实现及应用(堆排序和TOP-K问题)

    1.堆的知识点: 下面我们通过一张图片来更加深刻地理解堆 上面我们说过,堆的物理结构是一个数组,逻辑结构是一个完全二叉树,所以堆的实际结构类似于顺序表,只不过我们的处理方式类似于二叉树 那么我们就可以用顺序表那样的结构来表示堆了 于是我们可以写出这样的代码

    2024年02月07日
    浏览(53)
  • 【数据结构】二叉树-堆(top-k问题,堆排序,时间复杂度)

     🌈个人主页: 秦jh__https://blog.csdn.net/qinjh_?spm=1010.2135.3001.5343 🔥 系列专栏: 《数据结构》https://blog.csdn.net/qinjh_/category_12536791.html?spm=1001.2014.3001.5482 ​​ 目录 堆排序 第一种  ​编辑 第二种  TOP-K问题 建堆的时间复杂度 向下调整建堆的时间复杂度:  向上调整建堆的时间

    2024年01月21日
    浏览(61)
  • 数据结构进阶篇 之 【堆的应用】(堆排序,TOP-K问题)详细讲解

    所有人都关心我飞的高不高,只有我妈关心我翅膀硬不硬 1.1 建堆 1.2 利用堆删除思想来进行排序 –❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀-正文开始-❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀– 学习一个知识,我们起码要直

    2024年04月10日
    浏览(47)
  • 【数据结构】—堆排序以及TOP-K问题究极详解(含C语言实现)

                                            食用指南:本文在有C基础的情况下食用更佳                                          🔥 这就不得不推荐此专栏了: C语言                                        ♈️ 今日夜电波: ルミネセンス—今泉愛夏      

    2024年02月08日
    浏览(49)
  • 数据结构(C语言实现)——二叉树的概念及二叉树顺序结构和链式结构的实现(堆排序+TOP-K问题+链式二叉树相关操作)

    前面学习了数据结构中线性结构的几种结构,顺序表,链表,栈和队列等,今天我们来学习一种非线性的数据结构——树。由于二叉树是数据结构中的一个重点和难点,所以本文着重介绍二叉树的相关概念和性质,以及二叉树的应用。 树是一种非线性的数据结构,它是由n(

    2023年04月21日
    浏览(45)
  • Java 数据结构篇-实现堆的核心方法与堆的应用(实现 TOP-K 问题:最小 k 个数)

    🔥博客主页: 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍      文章目录         1.0 堆的说明         2.0 堆的成员变量及其构造方法          3.0 实现堆的核心方法         3.1 实现堆的核心方法 - 获取堆顶元素 peek()         3.2 实现堆的核心方法 - 下潜 do

    2024年02月04日
    浏览(54)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包