C语言数据结构二叉树之堆的实现和堆排序详解

目录
  • 一、本章重点
  • 二、堆
    • 2.1堆的介绍
    • 2.2堆的接口实现
  • 三、堆排序

一、本章重点

  • 堆的介绍
  • 堆的接口实现
  • 堆排序

二、堆

2.1堆的介绍

一般来说,堆在物理结构上是连续的数组结构,在逻辑结构上是一颗完全二叉树。

但要满足

  • 每个父亲节点的值都得大于孩子节点的值,这样的堆称为大堆。
  • 每个父亲节点的值都得小于孩子节点的值,这样的堆称为小堆。

那么以下就是一个小堆。

百度百科:

堆的定义如下:n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时,称之为堆。

若将和此次序列对应的一维数组(即以一维数组作此序列的存储结构)看成是一个完全二叉树,则堆的含义表明,完全二叉树中所有非终端结点的值均不大于(或不小于)其左、右孩子结点的值。由此,若序列{k1,k2,…,kn}是堆,则堆顶元素(或完全二叉树的根)必为序列中n个元素的最小值(或最大值)。

下面序列是堆的是( )。

A.97,56,38,66,23,42,12 //不是大堆也不是小堆,即不是堆。

B.23,86,48,3,35,39,42 //不是大堆也不是小堆,即不是堆。

C.05,56,20,23,40,38,29  //不是大堆也不是小堆,即不是堆。

D.05,23,16,68,94,72,71,73  //是小堆

只有D是堆而且是小堆,因此答案选D。

D的逻辑结构:

父亲节点和孩子节点的数组下标有以下关系:

  • left_child=(parent+1)*2
  • right_child=(parent+2)*2
  • parent=(child-1)/2(这里的child左孩子和右孩子都适用)

以上就不做证明了,不过我们可以验证一下,以上图D的逻辑结构为例,16的parent下标是2,72的下标是5,71的下标是6,满足left_child=(parent+1)*2、right_child=(parent+2)*2、parent=(child-1)/2。

有序一定是堆,堆不一定有序。

同时堆顶的数组是整个数组最大的数或者整个数组最小的数。

2.2堆的接口实现

第一件事我们就是要创建堆,实际就是创建一个数组,这里用动态数组。

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	size_t size;
	size_t capacity;
}HP;

堆创建好之后,我们需要对它进行初始化。

第一个接口:

void HeapInit(HP* php);

轻车熟路,将堆中的a置为NULL,size和capacity置为0。

或者这里可以设置capacity不为0的初始值也是可以的。

参考代码:

void HeapInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = php->capacity = 0;
}

我们对堆进行初始化之后,也要在最后销毁堆。

第二个接口:

void HeapDestroy(HP* php)

销毁堆,即销毁一个动态数组

参考代码:

void HeapDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
}

现在我们可以考虑往堆中插入数据了,要求插入新元素之后还是堆。

第三个接口:

void HeapPush(HP* php, HPDataType x)

堆没有要求在哪个位置插入新元素,可以在任意的位置插入新元素,但要保证插入新元素之后还是堆。

由于数组在头部还是在中间位置的插入复杂度是O(N),并且插入后不一定是堆了。

因此我们考虑的是直接在数组尾部插入新元素,然后用一个函数去调整数组的顺序使得它还是一个堆。

那么核心代码就是这个调整算法。

先来看这一个堆,插入新元素后该如何进行调整。

我们在数组的最后插入22,原堆是一个小堆,此时我们需要从下往上去调整各个父亲节点,使得该堆还是一个小堆。

换句话说:我们只需要调整下面有彩色的节点顺序。

交换过程:如果孩子节点小于父亲节点,那么将它们交换,然后迭代。

如果孩子节点大于父亲节点就跳出循环。

迭代过程:将父亲节点的下标赋值给孩子节点的下标,然后重新计算父亲节点的下标,计算方法:parent=(child-1)/2。

参考代码:

void AdjustUp(HPDataType* a, size_t child)
{
	size_t parent = (child - 1) / 2;
	while (child > 0)
	{
        //如果孩子小于父亲,则交换
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
        //孩子大于父亲,则结束调整
		else
		{
			break;
		}
	}
}
void HeapPush(HP* php, HPDataType x)
{
	assert(php);
    //动态数组,空间不够要扩容

	if (php->size == php->capacity)
	{
		size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = realloc(php->a, sizeof(HPDataType)* newCapacity);
		if (tmp == NULL)
		{
			printf("realloc failed\n");
			exit(-1);
		}

		php->a = tmp;
		php->capacity = newCapacity;
	}
    //尾插数据
	php->a[php->size] = x;
	++php->size;

	// 向上调整,控制保持是一个小堆
	AdjustUp(php->a, php->size - 1);
}

上面是多个数据的插入,那么如果插入第一个数据,这个函数还能帮助我们把数据插入堆中吗?

答案是肯定的。

既然有Push数据到堆,自然有从堆中删除元素了。

这里的删除不同于栈和队列的删除,这里指的是将堆顶的数据删除,删除之后堆还是一个堆。为什么只实现删堆顶的数据,因为简单实用,这个接口是为后面的堆排序做准备的。

第四个接口:

void HeapPop(HP* php)

思路比较简单:将数组第一个元素删除,然后保持它还是一个小堆。

怎么删除第一个数据呢?

这里的考虑是将数组第一个元素和数组最后一个交换,交换之后尾删掉最后一个元素,达成删除第一个元素的效果,复杂度是O(N),这里可以提一下,这种头删的方式是改变了数组元素的相对顺序的。

删除之后我们要做调整,使得堆还是小堆。

那么怎么调整呢?

以下是一个小堆

头删之后

如何调整它,使得它还是一个小堆?

这里的思路是:向下调整算法,首先parent=73,然后选出它子节点最小的值,然后它们之间交换,交换之后,将子节点看作新的父亲节点,继续向下调整,直到父亲节点的左孩子不存在。

参考代码:

void AdjustDown(HPDataType* a, size_t size, size_t root)
{
	size_t parent = root;
	size_t child = parent * 2 + 1;
	while (child < size)
	{
		// 1、选出左右孩子中小的那个
		if (child + 1 < size && a[child+1] < a[child])
		{
			++child;
		}

		// 2、如果孩子小于父亲,则交换,并继续往下调整
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

这里需要注意的是,为什么循环的结束条件不是右孩子不存在呢?

因为右孩子不存在时,也可能要进行交换。

比如:

还需要注意的是左孩子存在右孩子不一定存在

if (a[child+1] > a[child])
{
	++child;
}

直接这样写a[child+1]可能会越界,因此要加上child + 1 < size,保证child + 1 <= size-1。

参考代码:

void HeapPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
    //将数组第一个元素和最后一个元素交换然后删除最后一个元素,达到头删的目的。
	Swap(&php->a[0], &php->a[php->size - 1]);
	--php->size;
    //向下调整算法
	AdjustDown(php->a, php->size, 0);
}

其他接口补充:

由于比较简单,理解起来不费劲,因此这里直接给出。

参考代码:

bool HeapEmpty(HP* php)//判断堆是否为空
{
	assert(php);

	return php->size == 0;
}

size_t HeapSize(HP* php)//堆的元素个数
{
	assert(php);

	return php->size;
}

HPDataType HeapTop(HP* php)//取堆顶数据
{
	assert(php);
	assert(php->size > 0);

	return php->a[0];
}

三、堆排序

堆排序:利用堆顶节点是整个数组的最大值或者最小值的特点,可以达到排序的目的。

比如我们要将1、5、2、4、8、6、10排成升序

可以将这几个元素依次入堆,使得这些数据变成小堆。

然后我们可以取堆的第一个元素,它是整个数组最小的元素,要排升序,那么我们就需要将它排在第一个位置,然后删除堆顶元素,由于我们的删除接口的作用是:删除堆顶元素,并保持堆还是小堆,那么我们调用删除接口之后,再取堆顶元素,将它排在第二个位置,依次继续下去,我们就能将这些数据排成升序了。

参考代码:

void HeapSort(int* a, int size)
{
	HP hp;
	HeapInit(&hp);
    //建小堆
	for (int i = 0; i < size; ++i)
	{
		HeapPush(&hp, a[i]);
	}

    //不断取堆顶元素进行排序
	size_t j = 0;
	while (!HeapEmpty(&hp))
	{
		a[j] = HeapTop(&hp);
		j++;
		HeapPop(&hp);
	}
    //销毁堆,防止内存泄露
	HeapDestroy(&hp);
}

这里的堆排序的空间复杂度是O(N),因为在堆区开辟了一个N个元素大小的堆空间。

堆排序看起来挺复杂的,那么它的时间复杂度是什么呢?

建小堆:0(N)

HeapPop()一次执行的是:头删堆顶元素(O(1)),然后依次向下比较,比较的次数是高度次,因为是完全二叉树,比较的时间复杂度是O(logN)。

因此执行一次HeapPop的时间复杂度是O(logN)。

那么不断取堆顶元素进行排序,取了N个元素,调用了N次HeapPop(),时间复杂度是O(N*logN)。

总的时间复杂度是O(N)+O(N*logN),当N很大时,加的O(N)可以忽略。

实际时间复杂就是:O(N*logN)

空间复杂度:O(N)

那么堆排序的时间复杂度是O(N*logN)。

相比于冒泡排序的O(N*N)。

堆排序显然效率更高。

如果N等于100万,冒泡要执行1万亿次,而堆排序执行2千万次,效率可想而知!

到此这篇关于C语言数据结构二叉树之堆的实现和堆排序详解的文章就介绍到这了,更多相关C语言 堆排序内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C语言实现基于最大堆和最小堆的堆排序算法示例

    堆定义 堆实际上是一棵完全二叉树,其任何一非叶节点满足性质: Key[i]<=key[2i+1]&&Key[i]<=key[2i+2](小顶堆)或者:Key[i]>=Key[2i+1]&&key>=key[2i+2](大顶堆) 即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字. 堆排序的思想 利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性,使得每次从无序中选择最大记录(最小记录)变得简单. 最大堆:所有节点的子节点比其

  • C语言对堆排序一个算法思路和实现代码

    算法思想简单描述: 堆排序是一种树形选择排序,是对直接选择排序的有效改进. 堆的定义如下:具有n个元素的序列(h1,h2,...,hn),当且仅当满足(hi>=h2i,hi>=2i+1)或(hi<=h2i,hi<=2i+1)(i=1,2,...,n/2)时称之为堆.在这里只讨论满足前者条件的堆. 由堆的定义可以看出,堆顶元素(即第一个元素)必为最大项.完全二叉树可以很直观地表示堆的结构.堆顶为根,其它为左子树.右子树. 初始时把要排序的数的序列看作是一棵顺序存储的二叉树,调整它们的

  • C语言八大排序之堆排序

    目录 前言 一.堆排序的概念 二.堆排序的实现 第一步:构建堆 第二步:排序 三.完整代码 四.证明建堆的时间复杂度 前言 本章我们来讲解八大排序之堆排序.2022,地球Online新赛季开始了!让我们一起努力内卷吧! 一.堆排序的概念 堆排序(Heapsort):利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种.通过堆来进行选择数据,需要注意的是 排升序要建大堆,排降序建小堆. 堆排序使用堆来选数,效率就高了很多. 时间复杂度: 空间复杂度: 稳定性:不稳定 二.堆排序的实

  • C语言数据结构之堆排序源代码

    本文实例为大家分享了C语言堆排序源代码,供大家参考,具体内容如下 1. 堆排序 堆排序的定义及思想可以参考百度百科: 用一句概括,堆排序就是一种改进的选择排序,改进的地方在于,每次做选择的时候,不单单把最大的数字选择出来,而且把排序过程中的一些操作进行了记录,这样在后续排序中可以利用,并且有分组的思想在里面,从而提高了排序效率,其效率为O(n*logn). 2. 源代码 堆排序中有两个核心的操作,一个是创建大顶堆(或者小顶堆,这里用的是大顶堆),再一个就是对堆进行调整.这里需要注意的是,并没有真

  • C语言数据结构中堆排序的分析总结

    目录 一.本章重点 二.堆 2.1堆的介绍(三点) 2.2向上调整 2.3向下调整 2.4建堆(两种方式) 三.堆排序 一.本章重点 堆 向上调整 向下调整 堆排序 二.堆 2.1堆的介绍(三点) 1.物理结构是数组 2.逻辑结构是完全二叉树 3.大堆:所有的父亲节点都大于等于孩子节点,小堆:所有的父亲节点都小于等于孩子节点. 2.2向上调整 概念:有一个小/大堆,在数组最后插入一个元素,通过向上调整,使得该堆还是小/大堆. 使用条件:数组前n-1个元素构成一个堆. 以大堆为例: 逻辑实现: 将

  • C语言 数据结构堆排序顺序存储(升序)

    堆排序顺序存储(升序) 一: 完全二叉树的概念:前h-1层为满二叉树,最后一层连续缺失右结点! 二:首先堆是一棵全完二叉树: a:构建一个堆分为两步:⑴创建一棵完全二叉树      ⑵调整为一个堆 (标注:大根堆为升序,小根堆为降序) b:算法描述:①创建一棵完全二叉树 ②while(有双亲){ A:调整为大根堆: B:交换根和叶子结点: C:砍掉叶子结点: } c:时间复杂度为 O(nlogn)  ,空间复杂度为 O(1), 是不稳定排序! 代码实现: /*堆排序思想:[完全二叉树的定义:前

  • C语言数据结构之堆排序详解

    目录 1.堆的概念及结构 2.堆的实现 2.1堆的向下调整算法 2.2堆的向上调整算法 2.3建堆(数组) 2.4堆排序 2.5堆排序的时间复杂度 1.堆的概念及结构 如果有一个关键码的集合K = {k0,k1, k2,…,kn-1},把它的所有元素按完全二叉树(二叉树具体概念参见——二叉树详解)的顺序存储方式存储在一个一维数组中,并满足:Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0,1,2…,则称为小堆(或大

  • C语言实现堆排序的简单实例

    本文通过一个C语言实现堆排序的简单实例,帮助大家抛开复杂的概念,更好的理解堆排序. 实例代码如下: void FindMaxInHeap(int arr[], const int size) { for (int j = size - 1; j > 0; --j) { int parent = j / 2; int child = j; if (j < size - 1 && arr[j] < arr[j+1]) { ++child; } if (arr[child] &

  • C语言数据结构二叉树之堆的实现和堆排序详解

    目录 一.本章重点 二.堆 2.1堆的介绍 2.2堆的接口实现 三.堆排序 一.本章重点 堆的介绍 堆的接口实现 堆排序 二.堆 2.1堆的介绍 一般来说,堆在物理结构上是连续的数组结构,在逻辑结构上是一颗完全二叉树. 但要满足 每个父亲节点的值都得大于孩子节点的值,这样的堆称为大堆. 每个父亲节点的值都得小于孩子节点的值,这样的堆称为小堆. 那么以下就是一个小堆. 百度百科: 堆的定义如下:n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时,称之为堆. 若将和此次序列对应的一维数

  • C语言 数据结构之数组模拟实现顺序表流程详解

    目录 线性表和顺序表 线性表 顺序表 静态顺序表 动态顺序表 代码已经放在Gitee上,需要可以小伙伴可以去看看 用C语言数组模拟实现顺序表 Gitee 线性表和顺序表 线性表 线性表(linear list)是n个具有相同特性的数据元素的有限序列,这是我们广泛使用的数据结构. 线性表在逻辑上是线性结构,也就说是连续的一条直线.但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储. 常见的线性表:顺序表.链表.栈.队列.字符串- 顺序表 顺序表是用一段物理地址连

  • C语言数据结构二叉树简单应用

     C语言数据结构二叉树简单应用 在计算机科学中,二叉树是每个节点最多有两个子树的树结构.通常子树被称作"左子树"(left subtree)和"右子树"(right subtree),接下来我就在这里给大家介绍一下二叉树在算法中的简单使用: 我们要完成总共有 (1)二叉树的创建 (2)二叉树的先中后序递归遍历 (3)统计叶子结点的总数 (4)求树的高度 (5)反转二叉树 (6)输出每个叶子结点到根节点的路径 (7)输出根结点到每个叶子结点的路径. 定义二叉树结点类型

  • C语言数据结构二叉树先序、中序、后序及层次四种遍历

    目录 一.图示展示 (1)先序遍历 (2)中序遍历 (3)后序遍历 (4)层次遍历 (5)口诀 二.代码展示 一.图示展示 (1)先序遍历 先序遍历可以想象为,一个小人从一棵二叉树根节点为起点,沿着二叉树外沿,逆时针走一圈回到根节点,路上遇到的元素顺序,就是先序遍历的结果 先序遍历结果为:A B D H I E J C F K G 动画演示: 记住小人沿着外围跑一圈(直到跑回根节点),多看几次动图便能理解 (2)中序遍历 中序遍历可以看成,二叉树每个节点,垂直方向投影下来(可以理解为每个节点从最

  • C语言关于二叉树中堆的创建和使用整理

    目录 一.堆的创建 1.向上调整算法建堆 2.向下调整算法建堆 二.堆排序 1.建堆 2.利用堆删除思想来进行排序 一.堆的创建 下面我们先看一段代码: void HeapSort(int* a, int size) { // 建小(da)堆 HP hp; HeapInit(&hp); // O(N*logN) for (int i = 0; i < size; ++i) { HeapPush(&hp, a[i]);// O(N)空间复杂度 } HeapPrint(&hp);

  • C语言堆结构处理TopK问题详解

    目录 问题 分析 代码实现 问题 在一百万个数据中,求出最大的k个数字,怎么效率高. 1. 将一百万个数据排序,承接上一篇的堆排序,时间复杂度为O(N * LogN).但是显然这并不是最优解. 2. 一百万个数据放入一个数组中,将其视为一个完全二叉树,并用向下调整算法将其调整为一个大堆/小堆,然后Top/Popk次,即可求出前K个最大/最小的数字,时间复杂度为:O(N + K*LogN) 3. 用正确的堆处理TopK算法: 先假设求最大的K个数字,则建立大小为K的小根堆,然后在一百万-k个数据中

  • C/C++ 中堆和栈及静态数据区详解

    C/C++ 中堆和栈及静态数据区详解   五大内存分区 在C++中,内存分成5个区,他们分别是堆.栈.自由存储区.全局/静态存储区和常量存储区.下面分别来介绍: 栈,就是那些由编译器在需要的时候分配,在不需要的时候自动清除的变量的存储区.里面的变量通常是局部变量.函数参数等. 堆,就是那些由new分配的内存块,他们的释放编译器不去管,由我们的应用程序去控制,一般一个new就要对应一个delete.如果程序员没有释放掉,那么在程序结束后,操作系统会自动回收. 自由存储区,就是那些由malloc等分

  • C语言实现短字符串压缩的三种方法详解

    目录 前言 一.通用算法的短字符压缩 二.短字符串压缩 (1)Smaz (2)Shoco (3)Unisox2 三.总结 前言 上一篇探索了LZ4的压缩和解压性能,以及对LZ4和ZSTD的压缩.解压性能进行了横向对比.文末的最后也给了一个彩蛋:任意长度的字符串都可以被ZSTD.LZ4之类的压缩算压缩得很好吗? 本篇我们就来一探究竟. 一.通用算法的短字符压缩 开门见山,我们使用一段比较短的文本:Narrator: It is raining today. So, Peppa and George

  • C语言结构体成员赋值的深拷贝与浅拷贝详解

    目录 浅拷贝 结构体中不存在指针成员变量时 结构体中存在指针成员变量时 深拷贝 结论 浅拷贝 C语言中的浅拷贝是指在拷贝过程中,对于指针型成员变量只拷贝指针本身,而不拷贝指针所指向的目标,它按字节复制的.我们分几种情况举例子来看一下. 结构体中不存在指针成员变量时 代码如下: #include <stdio.h> typedef struct { char name[64]; int age; }Member; int main(){ Member stu1 = { "LiMing&

随机推荐