堆的基本操作和堆排序

作者介绍：一名正在学习编程技术的萌新，希望和大家一起进步。上传的内容，都是我学习过程中的笔记。
个人主页：个人主页
数据结构专栏：数据结构

堆的基本操作

1.什么是堆以及大小堆的概念

什么是堆？
堆在逻辑上是完全二叉树
通常用数组来存储
什么是大小堆？
大堆就是任何一个父节点都比对应的孩子节点大，小堆反之。

2.堆的父节点与孩子之间的关系

下标从零开始
parent=(child-1)/2
leftchild=parent*2+1
rightchild=parent*2+2

3.堆的结构定义

和顺序表很像

typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;
1
2
3
4
5
6

4.重点介绍几个堆常见的操作（都以小堆为样例）

a.向上调整算法

结束条件：孩子节点到了根或者已经满足堆的性质

代码样例

void AdjustUp(HPDataType*a,int child)
{
	int 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;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

b.向下调整算法

使用条件是必须先满足堆的性质

代码样例

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 = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

c.堆的删除操作

如果挪动覆盖的话，孩子与父亲的关系全乱了
所以选择首元素与尾元素交换，删除尾元素（也就是以前的根）的办法

void HeapPop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));
	swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;
	AdjustDown(php->a, php->size,0);
}
1
2
3
4
5
6
7
8

d.堆的插入操作

和顺序表的插入很像
稍微有点不同的就是每次插入都用用先上调整算法让它满足堆的性质

void HeapPush(HP* php, HPDataType x)
{
	assert(php);

	if (php->size == php->capacity)
	{
		int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, newCapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}

		php->a = tmp;
		php->capacity = newCapacity;
	}

	php->a[php->size] = x;
	php->size++;

	AdjustUp(php->a, php->size - 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

e.初始化和摧毁

相信读者朋友都会就不必啰嗦
为了文章的完整性在这里也把代码给出

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

void  HeapDestroy(HP* hp)
{
	free(hp->a);
	free(hp);
	hp->a = NULL;
	hp->capacity = 0;
	hp->size = 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

f.判空和返回根的值以及个数的操作

bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));
	return php->a[0];
}

int HeapSize(HP* php)
{
	assert(php);
	return php->size;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

堆排序

堆排序的两种方法

HeapSort1

void HeapSort1(HPDataType* a, int n)
{
	HP s;
	HeapInit(&s);
	for (int i = 0; i < n; i++)
	{
		HeapPush(&s, a[i]);
	}
	int i = 0;
	while (!HeapEmpty(&s))
	{
		//printf("%d ", HpTop(&s));
		a[i++] = HeapTop(&s);
		HeapPop(&s);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

这个方式每次排列的时候都要建立一个堆很麻烦，而且空间浪费比较大

HeapSort2

void HeapSort2(HPDataType* a, int n)
{

	//for (int i = 1; i < n; i++)
	//{
	//	AdjustUp(a, i);
	//}这样的效率没有倒着调高
	//因为它下面部分调的次数很多
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);//从最后一个父节点开始
	}
	int end = n-1;
	while (end>0)
	{
		swap(&a[0],&a[end]);
		AdjustDown(a, end, 0);//时间复杂度是O(N)
		end--;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

注意小堆是建立降序因为每次都把根弄到了最后

谢谢观看

若对你有所帮助，便是我更新的动力