数据结构——堆的应用 堆排序详解

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

💞💞 前言

hello hello~ ,这里是大耳朵土土垚~💖💖 ,欢迎大家点赞🥳🥳关注💥💥收藏🌹🌹🌹
数据结构——堆的应用 堆排序详解,数据结构,数据结构,c语言,排序算法

💥个人主页:大耳朵土土垚的博客
💥 所属专栏:数据结构学习笔记
💥对于数据结构顺序表、链表、堆有疑问的都可以在上面数据结构的专栏进行学习哦~
有问题可以写在评论区或者私信我哦~

在土土的上篇博客二叉树堆的介绍与实现中,我们发现测试代码是升序;今天我们就来分析堆的重要应用——**堆排序**🎉🎉。
升序实现如下:

#include"Heap.h"
int main()
{
	Heap hp;
	HeapInit(&hp);
	int a[] = { 65,100,70,32,50,60 };
	for (int i = 0; i < 6; i++)
	{
		HeapPush(&hp, a[i]);
	}
	while (!HeapEmpty(&hp))
	{
		int top = HeapTop(&hp);
		printf("%d\n", top);
		HeapPop(&hp);
	}
    HeapDestroy(&hp);
	return 0;
}

数据结构——堆的应用 堆排序详解,数据结构,数据结构,c语言,排序算法
详情可在土土的博客数据结构——lesson7二叉树堆的介绍与实现中查看🥳🥳

一、堆排序(基础版)

既然是堆排序,那我们首先肯定得有一个堆,这里土土就可以偷个懒将上篇博客中实现的堆代码copy一下🥰🥰

堆的实现

#include"Heap.h"
//堆的初始化
void HeapInit(Heap* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->capacity = 0;
	hp->size = 0;
}
// 堆的销毁
void HeapDestroy(Heap* hp)
{
	assert(hp);
	free(hp->a);
	hp->a = NULL;
	hp->capacity = 0;
	hp->size = 0;
}
//交换函数
void Swap(HPDataType* a,HPDataType* b)
{
	HPDataType tmp = *a;
	*a = *b;
	*b = tmp;
}

//堆向下调整算法
void AdjustDown(HPDataType* a, int n,int parent)
{
	//找到较小的孩子节点
	int child = parent * 2 + 1;
	
	//向下调整
	while (child < n)
	{
		if (child + 1 < n && a[child] > a[child + 1])
		{
			child++;
		}
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = child * 2 + 1;
		}
		else
			break;
		
	}
}

//向上调整
void AdjustUp(HPDataType* a,int child)
{
	//找到双亲节点
	int parent = (child - 1) / 2;
	//向上调整
	while (child > 0)
	{
		if (a[parent] > a[child])
		{
			Swap(&a[parent], &a[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
			break;
		
	}
}
// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	//判断容量
	if (hp->size == hp->capacity)//容量满了扩容
	{
		int newcapacity = hp->capacity == 0 ? 0 : 2 * hp->capacity;
		HPDataType* new = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity);
		if (new == NULL)
		{
			perror("realloc fail");
			return;
		}
		hp->a = new;
		hp->capacity = newcapacity;
	}
	//尾插
	hp->a[hp->size] = x;
	hp->size++;
	//向上调整算法
	AdjustUp(hp->a,hp->size-1);
}
// 堆的删除,删除堆顶元素
void HeapPop(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));
	Swap(&hp->a[0], &hp->a[hp->size - 1]);
	hp->size--;
	//向下调整算法
	AdjustDown(hp->a, hp->size, 0);

}
// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));
	return hp->a[0];
}
// 堆的数据个数
int HeapSize(Heap* hp)
{
	assert(hp);
	return hp->size;

}
// 堆的判空
int HeapEmpty(Heap* hp)
{
	assert(hp);
	return hp->size == 0;
}

当然在使用这些函数时要记得先声明一下,这里我们都放到一个头文件Heap.h中

Heap.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int HPDataType;
//构建一个结构体封装堆
typedef struct Heap
{
	HPDataType* a;//数组顺序表
	int size;//堆元素个数
	int capacity;//数组空间
}Heap;
//以下是实现堆的函数
// 堆的初始化
void HeapInit(Heap* hp);
// 堆的销毁
void HeapDestroy(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);


使用时只需包含该头文件即可
#include"Heap.h"

堆排序

给定一个数组a[ ] = {7,8,3,5,1,9,5,4},我们需要利用上面的堆来将它进行排序

🤩🤩思路
①我们首先需要将数组中的元素插入堆中(利用HeapPush函数),
💫前面我们已经学习过堆插入函数,它里面利用堆向上调整算法会自动将插入的数据调整为一个堆(我们实现的是小堆);
②然后我们需要获取堆顶元素(也就是小堆中最小的元素),利用HeapTop函数即可;
③获取最小元素后我们就需要获取次小元素,先利用堆的删除函数(HeapPop函数),将堆顶元素(也就是小堆中最小的元素)删除;
💞删除函数中堆向下调整算法又会将剩余元素调整为小堆,此时堆顶元素就是删除一个元素后最小的元素;
④将删除后的元素重新拷贝回数组a中;
⑤循环②③两步直到全部排序成功。

代码实现如下:

 #include"Heap.h"
void HeapSort(int* a,int size)
{
	Heap hp;
	HeapInit(&hp);
	//将a中元素插入堆中
	for (int i = 0; i < size; i++)
	{
		HeapPush(&hp, a[i]);
	}
	//获取堆顶(最小)元素并删除
	int i = 0;
	while (i < size)
	{
		a[i++] = HeapTop(&hp);
		HeapPop(&hp);
	}
	HeapDestroy(&hp);
}
int main()
{
	int a[] = { 7,8,3,5,1,9,5,4 };
	int size = sizeof(a) / sizeof(int);
	HeapSort(a,size);
	return 0;
}

🥳🥳结果如下:
排序前
数据结构——堆的应用 堆排序详解,数据结构,数据结构,c语言,排序算法
排序后
数据结构——堆的应用 堆排序详解,数据结构,数据结构,c语言,排序算法

💥💥上述堆排序的实现尽管能够实现排序,但是…我们发现如果没有提前实现堆或者准备好堆的代码,我们是没办法实现的,而且我们需要来回拷贝数据,空间复杂度较大。
🥰🥰这里就需要介绍下面简便版堆排序啦~

二、堆排序(简便版)

在土土的数据结构学习笔记数据结构——lesson7二叉树堆的介绍与实现中,详细介绍了堆向上调整算法与堆向下调整算法,接下来我们就可以利用这两个函数来实现堆以及堆的排序🥳🥳

(1)利用堆向上或向下调整算法实现堆

堆向上调整算法实现

//向上调整算法
void AdjustUp(HPDataType* a,int child)
{
	//找到双亲节点
	int parent = (child - 1) / 2;
	//向上调整
	while (child > 0)
	{
		if (a[parent] > a[child])
		{
			Swap(&a[parent], &a[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
			break;
		
	}
}

数组a[ ] = {7,8,3,5,1,9,5,4},我们可以看成一个二叉树:
数据结构——堆的应用 堆排序详解,数据结构,数据结构,c语言,排序算法
只需要从第二个数8开始每次读取一个数据都向上调整为堆,那么读完整个数组就可以得到一个堆啦~🥰🥰
数据结构——堆的应用 堆排序详解,数据结构,数据结构,c语言,排序算法
数据结构——堆的应用 堆排序详解,数据结构,数据结构,c语言,排序算法
数据结构——堆的应用 堆排序详解,数据结构,数据结构,c语言,排序算法
数据结构——堆的应用 堆排序详解,数据结构,数据结构,c语言,排序算法

//从第二个数据开始向上调整建堆
for (int i = 1; i < size; i++)
{
	AdjustUp(a, i);
}

🤩🤩之前基础版排序是又开辟了一个空间来存放a中的数据,排成堆后又每次选取最小的元素拷贝回a中,不仅麻烦而且会增加空间的使用;
所以简便版排序便直接将a看成一个二叉树利用向上调整算法直接成堆,不需要开辟额外的空间。

堆向下调整算法实现

🥰🥰类似于向上调整算法的实现,所不同的是开始调整的位置不再从第二个数开始,而是从最后一个非叶子节点开始向下调整:
数据结构——堆的应用 堆排序详解,数据结构,数据结构,c语言,排序算法
调整完了再依次往前找到前一个非叶子节点(下标是元素个数size-2再除2)重复向下调整即可;
🥳🥳使用向下调整的时间复杂度较向上调整小,所以我们这里选择用向下调整

代码如下:

//堆向下调整算法
for (int i = (size-2 )/ 2 ; i >= 0; i--)
{
	AdjustDown(a, size, i);
}

结果如下:
数据结构——堆的应用 堆排序详解,数据结构,数据结构,c语言,排序算法
数据结构——堆的应用 堆排序详解,数据结构,数据结构,c语言,排序算法

可以发现已经将其调整为一个小堆了🥳🥳

(2)利用堆向下调整算法排序

那我们应该怎么将堆中的元素排序呢?
🥳🥳这就要利用堆向下调整算法了

思路🥳🥳

①交换首尾元素,将堆中最小的元素(首元素)换到尾部;
②将交换后的尾部元素忽略,剩余元素利用堆向下调整算法(除头外左右子树都是堆)调整为堆;
数据结构——堆的应用 堆排序详解,数据结构,数据结构,c语言,排序算法
③重复②直到全部排完,得到降序数组:
数据结构——堆的应用 堆排序详解,数据结构,数据结构,c语言,排序算法

代码如下:

//排序
int end = size-1;//堆底元素下标
while (end)
{
	Swap(&a[0], &a[end]);
	AdjustDown(a, end, 0);
	end--;
}

🤩🤩Swap函数在这里:

//交换函数
void Swap(HPDataType* a, HPDataType* b)
{
	HPDataType tmp = *a;
	*a = *b;
	*b = tmp;
}

(3)完整实现🥳🥳

void HeapSort(int* a,int size)
{
	//堆向下调整算法
	 for (int i = (size-1 )/ 2 ; i >= 0; i--)
	{
		AdjustDown(a, size, i);
	}
	
	//排序
	int end = size-1;//堆底元素下标
	while (end)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}

}
int main()
{
	int a[] = { 7,8,3,5,1,9,5,4 };
	HeapSort(a, 8);

	return 0;
}

结果如下:
数据结构——堆的应用 堆排序详解,数据结构,数据结构,c语言,排序算法

✨✨思考:如果我们要排升序应该利用什么堆呢?相信大家通过上面的学习与理解都知道应该用大堆对不对?具体代码大家可以参考上面小堆实现降序来自己试着写一写哦~

三、结语

以上就是堆的应用——堆排序啦~,我们发现可以不用写堆的实现代码就可以将一个数组排成堆🥳🥳,关键在于堆向上调整与向下调整算法的理解与运用,大家都学废了吗 ,💞💞 完结撒花 ~🎉🎉🎉文章来源地址https://www.toymoban.com/news/detail-838616.html

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

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

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

相关文章

  • 数据结构入门(C语言版)二叉树的顺序结构及堆的概念及结构实现应用

    普通的二叉树是不适合用数组来存储的,因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用 顺序结构的数组来存储 ,需要注意的是 这里的堆和操作系统虚拟进程地址空间中的堆是两回事 ,一个是 数据结构 ,一

    2023年04月19日
    浏览(50)
  • 『初阶数据结构 • C语言』⑫ - 堆的概念&&实现(图文详解+完整源码)

    目录 0.写在前面 1.什么是堆? 2.堆的实现 2.1 堆的结构定义 2.2 函数声明 2.3 函数实现 2.3.1 AdjustUp(向上调整算法) 2.3.2 AdjustDown(向下调整算法) 2.3.3 HeapCreate(如何建堆) 2.3.4 建堆的时间复杂度 3. 完整源码 Heap.h文件 Heap.c文件  Test.c文件  上一章中介绍了树和二叉树的概念

    2024年02月16日
    浏览(46)
  • 【数据结构】堆:堆的构建,堆的向上调整算法,堆的向下调整算法、堆排序

    目录 一、堆的定义 1、堆的定义: 2、根节点与其左、右孩子间的联系   二、堆的创建 1、堆的向下调整算法  2、堆的向上调整算法  三、堆排序 1、堆的定义: 堆可以被看作是 一棵 完全二叉树 的 数组 对象 。即在 存储结构上是数组,在逻辑结构上是一棵完全二叉树 。在

    2024年01月22日
    浏览(43)
  • 【数据结构】堆的实现,堆排序以及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日
    浏览(49)
  • (Java)数据结构——排序(第一节)堆排序+PTA L2-012 关于堆的判断

    本博客是博主用于复习数据结构以及算法的博客,如果疏忽出现错误,还望各位指正。 堆排序是一种基于堆数据结构的排序算法,其核心思想是将待排序的序列构建成一个最大堆(或最小堆),然后将堆顶元素与最后一个元素交换,再将剩余元素重新调整为最大堆(或最小堆

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

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

    2024年02月05日
    浏览(50)
  • 数据结构——堆的应用

    堆结构主要有两个应用:1、堆排序 2、topK问题 现实中,排序是非常常见的,比如排序班级同学的各科分数,购物时,商品会按销量,价格,好评数等进行排序。相信大家也不喜欢再购物筛选时,加载半天出不来吧!一个好的排序用的时间会大大减少,改善用户的体验。堆排

    2024年04月10日
    浏览(76)
  • 数据结构--堆的实现-大根堆/小根堆/堆排序/堆排序稳定性证明/TOP-K

            前言          逆水行舟,不进则退!!!                目录        认识堆        堆的创建         1,向下调整的方法建立堆         2,以向下调整的方式建立小根堆         3,向上调整的方式建堆        堆的插入        堆的删除              

    2024年02月04日
    浏览(50)
  • 【数据结构】堆的实现(向下调整和向上调整法)和堆排序的实现

    目录 一、堆的概念引入 二、小堆的实现 ①、堆的初始化--HeapInit ②、小堆的向下调整法的实现 ③、堆排序的实现  ④、堆的插入和向上调整法  ⑤、删除堆顶数据 ⑥、获取堆顶 三、时间复杂度总结: 注:本文logN表示以2为底N的对数 普通的二叉树不适合用数组来存储的,因

    2024年02月03日
    浏览(38)
  • 数据结构之堆的应用

    在我们学习了堆之后我们知道,无论是大堆还是小堆,堆顶的元素要么最大,要么最小。 对于堆插入的时间复杂度为O(logn)也就是向上调整算法的复杂度,删除一个堆中的元素为O(logn),堆在我们日常生活中还是常用到的。 目录 1.top k问题(优质筛选问题) 2.堆排序 1.向

    2024年02月08日
    浏览(49)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包