【数据结构——堆】堆的基本功能和堆排序

【数据结构——堆】堆的基本功能和堆排序

文章目录

  • 前言
  • 一、堆的定义
    • 1.大根堆
    • 2.小根堆
    • 3.父亲和孩子之间的关系
  • 二、堆的操作和算法
    • 1.堆的初始化
    • 2.堆的插入
      • 向上调整算法
      • 向上调整算法时间复杂度
    • 3. 堆的删除
      • 向下调整算法
      • 向下调整算法时间复杂度:

前言

本文着重介绍什么是堆和堆的基本算法和基本功能以及堆排序。


一、堆的定义

堆的本质是一个数组,但是这个数组被看作成一棵完全二叉树

堆分为两种,大根堆和小根堆

1.大根堆

大根堆是每一个节点的值都大于它左右孩子节点的值。
如下图所示,这就是一个大根堆:每个父亲都大于它的孩子。

在这里插入图片描述

2.小根堆

小根堆与大根堆相反,每个父亲的节点值都小于它的孩子的值。

在这里插入图片描述

如图,这是一个小根堆,其父亲节点的值永远小于左右孩子的值。

当父亲节点的值等于孩子节点的值时,可以叫大根堆,也可以叫小根堆。

通过大根堆和小根堆可以看出,堆未必是有序的。

3.父亲和孩子之间的关系

知道任意父亲节点的下标,可以求出左孩子和右孩子的下标。

parent = (child-1)/2

左孩子或右孩子均可

左孩子:Lchild = parent * 2+1
右孩子:Rchild = parent * 2+2

如下图,当父亲节点为6,其下标为1时,

那么其左孩子下标为1*2+1 = 3

右孩子下标为 1*2+2 = 4

相反,如果知道左孩子下标为3,则其父亲的下标为 (3-1)/2 = 1
如果知道右孩子下标为4,则其父亲的下标为(4-1)/2 = 1

(除法法则向0的方向取整)

在这里插入图片描述

二、堆的操作和算法

1.堆的初始化

堆于栈或者顺序表类似,有一个malloc出来的数组和size值,以及capacity值。

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}PHP;
void HPInit(PHP* php);
void HPInit(PHP* php)
{
	assert(php);
	//初始状态设置容量4大小
	HPDataType* tmp = (HPDataType*)malloc(sizeof(HPDataType) * 4);
	assert(tmp);
	php->a = tmp;
	php->size = 0;
	php->capacity = 4;
}

2.堆的插入

在已有堆的基础上,向堆中插入一个数据,但是必须保证插入后,不会改变堆的结构。
也就是说,插入前是大堆,插入后也必须是大堆。

既要插入数据到合适的位置,又要不该变堆的结构,有一种算法可以解决该问题:

向上调整算法

在这里插入图片描述

以该图片的例子为例:在已有堆的基础上插入一个60:
在这里插入图片描述

这个按照原来的堆是大堆这个60是所有元素中最大的数,应该插入到堆顶上。

注意:不能使用挪动数据的方法,即把所有元素往后挪一位进行插入,
1.挪动数据时间复杂度O(n),效率低
2.挪动已经改变了原来堆的结构,挪动之后很有可能不再是堆了。
3.如果插入的数据不是最大的或最小的,无法判断该往哪个地方插入。

向上调整算法流程如下:
假设原本的堆是大堆
1.记录该插入元素的父亲的下标。

2.将要插入的元素和其父亲做比较,如果孩子大于父亲,那么将孩子和父亲进行交换。

3.父亲和孩子迭代往上走,再进行判断,重复第二步的过程。

在这里插入图片描述

实现代码如下:

void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	//不能用这样的循环写法,有潜在的越界风险
	//while(parent>=0)
	//因为parent不会小于0,当child为0时,child-1 = -1,-1/2 = 0,parent最小也是0,不会结束while循环
	//但是这段代码是能正常运行的,因为只要child小于parent了,那就break。
	while (child > 0)
	{
		//现在是大堆,如果要小堆,就改一下成小于号
		if (a[child] > a[parent])
		{
			swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

注意:
在循环条件判断时,不能用parent>=0来作为继续条件,
1.parent不会是负数,因为当child为0 时,
parent = (child-1)/2 = 0,这个条件不会终止循环
所以只能用child>0来进行终止。

总插入代码如下:

void HPPush(PHP* php, HPDataType x)
{
	assert(php);
	//插入之前先判断容量
	if (php->size == php->capacity)
	{
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * php->capacity * 2);
		assert(tmp);
		php->a = tmp;
		php->capacity *= 2;
	}
	//开始插入
	php->a[php->size++] = x;
	//插入完成后,开始向上调整
	AdjustUp(php->a, php->size - 1);
}

向上调整算法时间复杂度

在这里插入图片描述

假设这个堆的高度为h,则在最坏情况下,最后一层的每个节点向上调整的次数为(h-1)次,一共有2^(h-1)个节点,那么最后一层调整的总次数为 :2^(h-1)*(h-1)次,假设总调整次数为T(N)次,由于第一个节点不需要调整,则有:

在这里插入图片描述

由错位相减法:
在这里插入图片描述

推导如上:则整个过程向上调整算法的时间复杂度为O(N*logN)

注意:如果单独调整某个数字,则时间复杂度为logN

3. 堆的删除

假设一个堆为大根堆,
对于堆的删除来说,删除堆尾元素没有意义,删除堆顶元素才有意义,因为堆顶元素是最大的,只有把最大的元素删除了,才能筛选出次大的,只有把次大的元素删除了,才能筛选出次次大的,这样即可以达到一个排序的效果也不会破坏堆的结构。

注意:堆的删除同样不能使用数组往前覆盖的方法进行删除。
1.往前覆盖时间复杂度O(N),效率不高
2.往前覆盖会导致堆的父子关系和兄弟关系造成紊乱,破坏了堆的结构。

向下调整算法

所以堆的删除使用向下调整的算法:

步骤如下:
假设是大根堆的条件下:
1.交换堆顶和堆尾的两个数据,这样堆的最大元素就被删除了。
2.为了保证堆的结构不会被改变,需要把现在堆顶的元素向下调整。先记录堆顶下标,即parent,再记录孩子下标,因为可能有左孩子和右孩子,不知道谁大,那么我们先假设左孩子大,然后再将左孩子和右孩子进行比较,谁大就再跟父亲进行比较,如果父亲小于孩子,那么父亲就要向下调整。

在这里插入图片描述

实现代码如下:

//1.向下调整算法一开始是用来实现堆的删除的
//删除是专门用来删除堆顶元素的,这样才有意义
// 假如是一个大根堆,那就把堆顶删了,把老大删了,这样才能筛选出老二
//把老大删了的做法:把堆顶元素和最后一个元素交换,然后size--
//然后堆顶元素和左右孩子比较,大的孩子做堆顶,这样就实现了推老二上堆顶。
//然后这个在老二位置的这个元素继续向下调整,就是实现了堆的删除
//删除堆顶元素又保证了原来是大堆,删除之后还是大堆的情况,不会导致兄弟父子关系错乱。
//删除堆顶元素不能用向上调整的算法,因为用向上调整
//2.后来向下调整算法不仅仅可以用来进行堆的删除元素
//还可以用来实现建堆,下面会提及
void AdjustDown(HPDataType* a, int n, int parent)
{
	//假设左孩子就是最大的
	int child = (parent * 2) + 1;
	while (child < n)
	{
		//筛选左右孩子谁大
//		if(a[child+1]>a[child]),不能这样判断
		//(因为有可能存在右孩子不存在的情况,需要判断一下右孩子是否存在)
		//否则容易出现越界问题
//		if (a[child + 1] > a[child] && child + 1 < 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;
		}
	}
}

注意:在比较左右孩子的大小时,不能直接判断,要先判断右孩子是否存在。

注释有些重要的细节,请认真查看。

向下调整算法时间复杂度:

向下调整不同于向上调整,向下调整节点开始调整是从第一个非叶子节点开始调整的:

在这里插入图片描述

因为最后一排不需要向下调整
推导如下:
在这里插入图片描述

所以向下调整算法的时间复杂度为O(N)

注意:如果单独调整某个数字,则时间复杂度为logN

有一个比较好的方法判断向上调整快还是向下调整快:
直接看堆的最后一行,

向上调整算法中:堆的最后一行调整次数为2^(h-1)*(h-1)次,

向下调整算法中:堆的最后一行不需要调整,

倒数第二行才需要调整,且调整次数为2^(h-2)* 1。

对比对比就知道了。

                       

点击阅读全文

上一篇 2023年 6月 14日 am11:13
下一篇 2023年 6月 14日 am11:15