当前位置: 首页 > article >正文

初阶数据结构(C语言实现)——5.3 堆的应用(1)——堆排序

目录

  • 1 堆的应用
    • 1.1 堆排序
      • 1.1.1 思路
      • 1.1.2 代码实现
    • 1.2 建堆的时间复杂度
      • 1.2.1 向下调整
      • 1.2.1 向上调整
      • 1.2.3 结论

学习堆的应用之前,欢迎学习下堆。
这是博主之前的文章,欢迎学习交流

初阶数据结构(C语言实现)——5.2 二叉树的顺序结构及堆的实现
初阶数据结构(C语言实现)——5.1二叉树基础概念

1 堆的应用

1.1 堆排序

1.1.1 思路

堆排序即利用堆的思想来进行排序,总共分为两个步骤:

  1. 建堆
    升序:建大堆
    降序:建小堆
  2. 利用堆删除思想来进行排序
    建堆和堆删除中都用到了向下调整,因此掌握了向下调整,就可以完成堆排序。
    在这里插入图片描述

在这里插入图片描述

1.1.2 代码实现

void swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType x = *p1;
	*p1 = *p2;
	*p2 = x;
}

 void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;//根据孩子位置,计算父亲位置
	while (child > 0)//child = 0,说明parent不存在了,已经到堆顶了
	{
		if (a[child] > a[parent]) //当孩子大小大于父亲大小的时候就交换
		{
			swap(&a[child], &a[parent]);//因为其他地方也要用到交换,封装了一个交换函数
			child = parent; //现在把父亲的值给孩子。
			parent = (child - 1) / 2;//继续计算现在节点的父亲结点,
		}
		else//孩子<=父亲 没必要往上走,直接break就行。		
		{
			break;
		}
	}
}
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+1<n放前面,否则后面a[child+1]就越界了!
		{
			++child;
		}
		//交换
		if (a[child] > a[parent])
		{
			swap(&a[child],&a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
// 排升序 -- 建大堆
 void Heapsort(int* a, int n)//参数:数组和数据个数
{
	 //建堆,方法1:向上调整堆 //模拟的是插入数据的过程
	 for (int i = 1; i < n; ++i)
	 {
		 AdjustUp(a, i);
	 }
	 //建堆,方法2:向下调整堆
	 for (int i = 1; i < n; ++i)
	 {
		 AdjustDown(a, n , i);
	 }


	 int end = n - 1;
	 while (end > 0)
	 {
		 swap(&a[end], &a [0]);
		 AdjustDown(a, end, 0);
		 --end;

	 }
}

1.2 建堆的时间复杂度

1.2.1 向下调整

因为堆是完全二叉树,而满二叉树也是完全二叉树,此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值,多几个节点不影响最终结果):

在这里插入图片描述

因此:向下建堆的时间复杂度为O(N)。

1.2.1 向上调整

在这里插入图片描述

因此向上建堆的时间复杂度是N*logn

1.2.3 结论

向下调整时间复杂度更小,更优,所以建堆使用的是向下调整


http://www.kler.cn/a/584199.html

相关文章:

  • qt5中使用中文报错error: C2001: 常量中有换行符
  • Python入门教程:从零开始学习Python编程
  • Houdini Labs Building Generator入门学习
  • RestTemplate 发送 JSON 请求时为何要手动序列化对象?
  • 用SpringBoot做一个web小案例实现登录
  • 16天 - 单例模式有哪几种实现?如何保证线程安全?什么是策略模式?一般用在什么场景?什么是模板方法模式?一般用在什么场景?
  • Linux中的基本指令(下)
  • 【文献阅读】Zotero 新手完全教程:安装、使用与插件
  • Python Cookbook-4.2 通过列表推导构建列表
  • 【C++】 —— 笔试刷题day_3
  • C++ Primer Plus第十二章课后习题总结
  • 人工智能与我何干
  • 新闻网页信息抽取
  • OKHttp3 源码阅读 - Kotlin版本
  • IIC通信协议详解与STM32实战指南
  • 如何在Ubuntu上构建编译LLVM和ISPC,以及Ubuntu上ISPC的使用方法
  • Fiora聊天系统本地化部署:Docker搭建与远程在线聊天的实践指南
  • 广告牌倾斜安全监测:保障公共安全的智能化解决方案
  • OpenMCU(三):STM32F103 FreeRTOS移植
  • 【学习笔记】《逆向工程核心原理》03.abex‘crackme-2、函数的调用约定、视频讲座-Tut.ReverseMe1