数据结构堆详解

@[TOC]堆详解

一，堆

1.1堆的概念

堆的性质：
堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。

1.2堆的存储模式

我们前面的文章提到过，二叉树的两种存储模式，一个是顺序存储，一个链式存储。而堆就是顺序存储的典型。

这里还有几个关系式要牢牢记住

1. parent=(child-1)/2
2. leftchild=parent*2+1
3. rightchild=parent*2+2

二，堆的实现

void Swap(HPDataType* p1, HPDataType* p2);
void HeapPrint(HP* php);


void HeapInit(HP* php);
void HeapDestroy(HP* php);
void HeapPush(HP* php, HPDataType x);
void HeapPop(HP* php);
int HeapTop(HP* php);
bool HeapEmpty(HP* php);
1
2
3
4
5
6
7
8
9
10

2.1堆的结构

从上面的图我们也能看出其实堆就是数组，所以堆的结构和顺序表的结构是一模一样的。

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

2.2★★★堆的插入

堆的插入和顺序表叶类似，先判断空间是否够大，然后在插入数据，不过堆的插入有一个重点就是向上调整

向上调整

我们在尾插入5的时候，就跟自己的父节点比较，（这里是建小堆）比父节点比较，如果更小那就交换。再跟上面的比较，最坏的情况就是到跟节点，

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

所以堆的插入的代码如下

void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	//扩容
	if (php->capacity == php->size)
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a,sizeof(HPDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(-1);
		}
		php->capacity = newcapacity;
		php->a = tmp;
	}
	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

2.3★★★堆的删除

我们说堆的删除的时候，一般指的是删除跟位置的值，那么我们最开始学习的时候，想到的删除方法就是直接删掉跟，然后底下的数据在依次组成堆，但是我们在这样做的时候就会发现，兄弟变成父与子的关系，那么就不一定会是堆的结构了，因为不论是大堆还是小堆，兄弟节点之间没有大小的区分，所以就不能保证堆的正确建立。
所以我们就有了以下的方法，
1.先把根和最后一个节点交换，然后删掉最后一个节点，
2.在依次向下调整这样就可以保证堆的正确性。

向下调整

向下调整和向上调整思路比较类似，向下调整就是知道了父亲节点的下标，然后依次向下比较。

//向下调整
void AdjustDown(HPDataType* a,int n, int parent)
{
	int child = parent*2 + 1;
	while (child<n)
	{
		if (a[child + 1] > a[child] && child + 1 < n)
		{
			++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

那么堆的删除代码就是：

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);
}
1
2
3
4
5
6
7
8
9

2.4取堆顶的数据

int HeapTop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	return php->a[0];
}
1
2
3
4
5
6

2.5判断是否为空

bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}
1
2
3
4
5

三，总结

我们已经把堆的基本框架学完了，下一节我们就要学习堆排序的内容。
还是一样，反复练习百炼成钢。