堆排序(大根堆与小根堆)

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

(1)是什么?

是一种适用于关键字较多的情况下的排序算法,例如在十亿个数中选出前1000个最大值或者最小值
如果在传统的排序算法中(例如冒泡,插入等),我们习惯把目标数据整体进行一次排序,再截取出前1000个最小的或者最大的。
但是我们可以设想一下,从一开始我们目标就只要1000个,那么其实其余九亿九千九百九十九万九千个数据,我们压根不需要知道它们的排序顺序,只需要知道它们都比我们1000个目标数据中最大值都要大就可以了
这就是堆排序。

它的思想整体上非常清晰简单,结构上是一个完全二叉树。
根结点比左右孩子都大则叫做大根堆。其中,左右孩子的根结点,又会比它们的左右孩子都大。
根结点比左右孩子都小则叫做小根堆。其中,左右孩子的根结点,又会比它们的左右孩子都小。
更简单点说:所有中间结点,一定比它孩子大(大根堆),或者一定比它的孩子小(小根堆)

(2)如何构建大根堆

初始化:

1:按照给出的数组,首先按照层次优先(逐层摆放)构造一棵二叉树
2:从该二叉排序树的最后一个叶子结点的根结点出发,比较该结点的左右孩子,选取最大的置换到根结点上
3:整理倒数第二非叶子结点,比较并选择一个最大的置换到根结点…
4:依次类推,直到整理完整棵树,此时树的根结点一定是该大根堆中最大值
5:在把大数往上顶的过程中,也要看互换位置的数是否比左右孩子都大,如果不是,则又要选择一个最大的换到该子树根结点。

例如:假设有数组【1,3,5,7,9,2,4,6,8,10】要求建立大根堆

1:先按照层次优先原则建立二叉树(该树生成后默认按照行遍历存放在一个一维数组中,且该数组下标从1开始,即下标为1存放着根结点1,下标2存放左孩子2,下标3存放着右孩子5,以此类推)
堆排序(大根堆与小根堆)

2:从该二叉树的最后一个非叶子结点出发,比较该结点的左右孩子,选取最大的置换到根结点上
如何找到二叉树最后一个非叶子结点:n/2向下取整
该例子中,10个元素,则10/2 = 5;即最后一个非叶子结点下标是5,也就是根结点值为9的子树。
比较9,10,发现10最大,于是10和9交换位置。

3:整理倒数第二非叶子结点,比较并选择一个最大的置换到根结点…
如何找到倒数第二个非叶子结点:n/2 - 1 = 4
也就是下标为4的,根结点值为7的子树
比较6,7,8,于是7和8交换位置,8作为根结点。

4:依次类推,直到整理完整棵树,此时树的根结点一定是该大根堆中最大值
5:在把大数往上顶的过程中,也要看互换位置的数是否比左右孩子都大,如果不是,则又要选择一个最大的换到该子树根结点。
堆排序(大根堆与小根堆)

到这里就完成了大根堆的构建

输出栈顶元素:

当输出栈顶的10后,固定用【最后一个叶子结点】1补上,发现1破坏了大根堆的性质,于是要从根结点往下调整,也就是比较1,9,5;把9放根结点。
1下沉到左子树根结点,但是还是不满足大根堆性质,于是比较1,8,3;把8放到左子树根结点,1再次下沉到左子树的左子树的根结点中
比较1,6,7;把7替换到左子树的左子树的根结点,把1再次下沉。
至此,重新调整的二叉树又符合大根堆性质了。
堆排序(大根堆与小根堆)

新增/插入元素操作:

新增/插入的元素都是把新结点放在新生成的最后一个叶子结点中,然后比较该新叶子结点数据的值与它父结点的值的大小,看是否需要换位置,如果需要,则开始调整,这跟初始化时候一样的操作。文章来源地址https://www.toymoban.com/news/detail-494940.html

⚠️注意,初始化和新增元素都是由下至上的调整,而删除了栈顶元素,是由上至下的调整。

代码实现:

#include <stdio.h>

void HeapSort(int a[], int i, int lenght){
	/*用以保存子树的根结点*/
	a[0] = a[i];
	/* 按照二叉树性质,不断i*2是不断深入找到下一层的左孩子结点 */
	for(int j=i*2; j<=lenght; j=j*2){
		/* k是对应子树的右孩子结点,先比较右孩子 */
		int k = j+1; 
		/* 左右孩子比较出一个大值 */
		if(k<lenght && a[k]>a[j]){
			j = k;
		}
	    /* 判断根结点与左右孩子的最大值谁更大 */
		if(a[0]<a[j]){
			a[i] = a[j];
			i = j;
		}
	}
	/* 循环退出后,j一定是最适合temp值的地方 */
	a[i] = a[0];
}

int main()
{
	int a[]={0,1,3,5,7,9,2,4,6,8,10};
	int lenght = 11;
	/* 从下往上逐个非叶子结点调整 */
	for(int i=lenght/2; i>0; i--) {
		HeapSort(a,i,lenght);
	}
   
   return 0;
}


到了这里,关于堆排序(大根堆与小根堆)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【数据结构】详解二叉树与堆与堆排序的关系

    🌇个人主页:平凡的小苏 📚学习格言:别人可以拷贝我的模式,但不能拷贝我不断往前的激情 🛸C语言专栏:https://blog.csdn.net/vhhhbb/category_12174730.html 🚀数据结构专栏:https://blog.csdn.net/vhhhbb/category_12211053.html         家人们更新不易,你们的👍点赞👍和⭐关注⭐真的对我

    2024年02月02日
    浏览(42)
  • Ubuntu是一种现代化的开源Linux操作系统,适用于企业服务器、桌面电脑、云和IoT物联网设备

    Ubuntu是一种现代化的开源Linux操作系统,适用于企业服务器、桌面电脑、云和IoT物联网设备。您可以从Ubuntu官网下载Ubuntu桌面版、Ubuntu服务器版、Ubuntu for Raspberry Pi和IoT设备版、Ubuntu Core以及所有Ubuntu版本。 Ubuntu是一种现代化的开源Linux操作系统,它适用于广泛的设备和应用场

    2024年01月16日
    浏览(72)
  • 算法基础:堆【以大根堆为例】

    二叉堆的逻辑结构就是一棵完全二叉树,所以也叫完全二叉堆 ◼️ 鉴于完全二叉树的一些特性,二叉堆的底层(物理结构)一般用数组实现即可 ◼️ 索引 i 的规律( n 是元素数量) 如果 i = 0 ,它是根节点 如果 i 0 ,它的父节点的索引为 floor( (i – 1) / 2 ) (向下取整) 如果 2i

    2024年02月07日
    浏览(22)
  • 【数据结构】5.大根堆和左高树

    大根树: 树中的每一个节点的值都大于或等于其子节点的值 大根堆: 既是大根树又是完全二叉树(增加了完全二叉树的限制条件)所以下图中只有(a)和(c)是大根堆 假设在下面大根堆中插入一个元素9,插入步骤如下,时间复杂度为O(height)=O(logn) 尝试插入在6号位置,如果新的

    2024年02月08日
    浏览(28)
  • 项目开发中什么场景下Redis适用?

    Redis是一种开源的内存键值存储系统,具有高性能、高可靠、持久化、可扩展等特点,因此在许多场景下都非常适用。 缓存场景 数据库查询缓存:在Web应用中,频繁的数据库查询是一项昂贵的操作,会消耗大量的计算资源和时间。使用Redis作为数据库查询的缓存层,可以将查

    2024年01月21日
    浏览(39)
  • 【MongoDB】什么是MongoDB?MongoDB有什么特点?MongoDB的适用场景?

    MongoDB是一个 开源、高性能、支持海里数据存储的文档型数据库。 MongoDB是一个高效的非关系型数据库(不支持表关系:只能操作单表) MongoDB是一个介于关系数据库和非关系数据库之间的产品,是非关系数据库当中功能最丰富,最像关系数据库的,它支持的数据结构非常松散

    2023年04月21日
    浏览(61)
  • 蓝桥杯双周赛算法心得——通关(哈希+小根堆)

    大家好,我是晴天学长,这是很重要的贪心思维题,哈希的存法和小根堆的表示很重要。💪💪💪 1) .通关 2) .算法思路 通关 用hash(int[])存点的子节点并按输入顺序存关卡的号码(输入顺序就是) 列如:key:父节点 难度 经验 关卡 优先队列存难度和节点 1.接受数据和初始

    2024年02月08日
    浏览(36)
  • 为什么 PostgreSQL 的适用性很强?

    说起使用数量最大的数据库SQLite 它是全球最广泛部署的数据库引擎。它存在于你的手机中,存在于你的浏览器中,如果你搜索你的电脑,你也会在其中找到它的 .db 文件。SQLite 受到 Postgres 的启发。其作者 Richard Hipp 称 SQLite 是 Postgres 的“概念分支”。两者没有共享代码,但是

    2024年02月16日
    浏览(36)
  • HTTP常见的状态码有哪些?适用场景有什么?

    1、什么是HTTP状态码 HTTP状态码 (英语:HTTP Status Code),用以 表示网页服务器 http 响应状态 的3位数字代码。 HTTP状态码的作用是服务器告诉客户端当前请求响应的状态,通过状态码就能判断和分析服务器的运行状态。 2、常见的状态码和适用场景 状态码第一位数字决定了不

    2023年04月24日
    浏览(42)
  • Redis可以用作数据库吗?它的适用场景是什么?

    是的,Redis可以用作数据库。虽然Redis通常被认为是一个内存数据库(in-memory database),但它也可以通过持久化机制将数据保存在磁盘上,以便在重启后恢复数据。 Redis的适用场景包括但不限于以下几个方面: 缓存:Redis的高性能、低延迟和良好的缓存策略使得它非常适合作为

    2024年02月13日
    浏览(40)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包