作者：一个喜欢猫咪的的程序员 

专栏：《数据结构》

喜欢的话：世间因为少年的挺身而出，而更加瑰丽。                                  ——《人民日报》

---

目录

堆的概念及结构：

堆的实现思路：（我们以大堆为例）

需要实现的接口：

 实现的一些细节：

HeapPush函数：

Ajustup函数：

HeapPop函数：

Ajustdown函数： 

代码实现：

Heap.h文件：

Heap.c文件:

Test.c文件：

---

堆的概念及结构：

如果有一个关键码的集合K = { ， ， ，…， }，把它的所有元素按完全二叉树的顺序存储方式存储
在一个一维数组中，并满足： <= 且 <= ( >= 且 >= ) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

• 父节点都比其的子节点大的完全二叉树叫做大堆。
• 父节点都比其的子节点小的完全二叉树叫做小堆。

 堆的性质：

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

---

堆的实现思路：（我们以大堆为例）

需要实现的接口：

void Swap(HPDataType* p1, HPDataType* p2);
void HeapCreate(HP* php, HPDataType* a, int n);
void HeapPrintf(HP* php);
void HeapInit(HP* php);
void HeapDestroy(HP* php);
void HeapPush(HP* php, HPDataType x);
void HeapPop(HP* php);
HPDataType HeapTop(HP* php);
int HeapSize(HP* hp);
bool HeapEmpty(HP* hp);
void Ajustdown(HPDataType* a, int n, int parent); 
void Ajustup(HPDataType* a, int n);

从堆的结构中，我们了解到堆是一个数组a，并且后续我们可能需要对数组进行扩容和缩小，因此我们还需要两个变量：有效长度size和容量capacity

 

---

 实现的一些细节：

 HeapInit、HeapDestroy、HeapPrintf函数没有什么好说的。

void HeapInit(HP* php)
{
	assert(php);
	php->capacity = 0;
	php->size = 0;
	php->a = NULL;
}
void HeapDestroy(HP* php)
{
	assert(php);
	assert(php->a);
	free(php->a);
	free(php);
}
void HeapPrintf(HP* php)
{
	assert(php);
	for (int i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}

HeapPush函数：

因为我们的存储结构是一个数组，Push就直接添加数据吗？

当capacity==size时扩容一下（包括初始化的方案），当size==0时，扩容4个空间，否则扩容二倍的空间，capacity也跟着扩大，当push后size++。

 以大堆为例：

100比30大，30和100需要调换位置，然后100又比70大，70和100需要再次调换位置。

我们添加的数据x作为子节点child，child可能会比它的父节点parent大。因此需要将child向上调整Ajustup。

void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		int newcapacity=php->capacity == 0 ? 4 : 2 * php->capacity;
		HPDataType* tmp=(HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->size++] = x;
	Ajustup(php->a, php->size-1);
}

Ajustup函数：

•  二叉树的性质：child=2*parent+1

(可参考我的另外一篇博客：http://t.csdn.cn/GLlHN)

 如果child<parent时，child和parent交换，交换后child=parent。否则break跳出循环。以此循环，当child来到根节点时结束，即：下标为0。

void Ajustup(HPDataType*a, int child)
{//N*logN
	assert(a);
	//int child = n - 1;
	while (child > 0)
	{
		int parent = (child - 1) / 2;
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
		}
		else
		{
			break;
		}
	}
}

 交换可以写一个函数Swap来复用，会用到很多次。

void Swap(HPDataType* p1, HPDataType* p2)
{
	assert(p1);
	assert(p2);
	HPDataType tmp = 0;
		tmp = *p1;
		*p1 = *p2;
		*p2 = tmp;
}

---

HeapPop函数：

出数据只能是出堆顶的元素（根节点），否则没有什么意义。

当我们将根节点删除后，它的左子节点leftchild和右子节点rightchild谁来当根节点呢？ 并且我们还得维持它是一个堆，也就是维持它是一个完全二叉树。

假设左子节点大于右子节点时，让左子节点当根节点会出现什么情况呢？

显然这种方法是不可行的！！！

 换一种思路：

让第一个位置的值和最后一个位置的值，再size--不就相当于删除了嘛，但交换上去的值在根节点的位置上，我们无法维持是大堆的情况，因此还需要向下调整Ajustdown。

void HeapPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	Swap(&php->a[0], &php->a[php->size-1]);
	php->size--;
	Ajustdown(php->a, php->size-1 , 0);
}

Ajustdown函数： 

• 由性质child=2*parent+1，反推：parent=（child-1）/2。

假设左子节点大，左子节点leftchild大于右子节点rightchild ，当左子节点小于右子节点，child++找到子节点大的那一个。

当parent>child时交换，parent=child、child=2*child+1。

void Ajustdown(HPDataType* a, int n,int parent)
{//O(N)
	assert(a);
	int child = 2 * parent+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 = child * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

HeapTop、HeapSize、HeapEmpty函数较为直接，就不做解释了。

HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	return php->a[0];
}
int HeapSize(HP* php)
{
	assert(php);
	return php->size;
}
bool HeapEmpty(HP* php)
{
	assert(php);
	if (php->size == 0)
		return true;
	else
		return false;
}

---

代码实现：

Heap.h文件：

#define  _CRT_SECURE_NO_WARNINGS
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
#include<string.h>
#include<time.h>
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;
void Swap(HPDataType* p1, HPDataType* p2);
void HeapCreate(HP* php, HPDataType* a, int n);
void HeapPrintf(HP* php);
void HeapInit(HP* php);
void HeapDestroy(HP* php);
void HeapPush(HP* php, HPDataType x);
void HeapPop(HP* php);
HPDataType HeapTop(HP* php);
int HeapSize(HP* hp);
bool HeapEmpty(HP* hp);
void Ajustdown(HPDataType* a, int n, int parent); 
void Ajustup(HPDataType* a, int n);

Heap.c文件:

#include"Heap.h"
void HeapInit(HP* php)
{
	assert(php);
	php->capacity = 0;
	php->size = 0;
	php->a = NULL;
}
void HeapDestroy(HP* php)
{
	assert(php);
	assert(php->a);
	free(php->a);
	free(php);
}
void HeapPrintf(HP* php)
{
	assert(php);
	for (int i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}
void Swap(HPDataType* p1, HPDataType* p2)
{
	assert(p1);
	assert(p2);
	HPDataType tmp = 0;
		tmp = *p1;
		*p1 = *p2;
		*p2 = tmp;
}
void Ajustup(HPDataType*a, int child)
{//N*logN
	assert(a);
	//int child = n - 1;
	while (child > 0)
	{
		int parent = (child - 1) / 2;
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
		}
		else
		{
			break;
		}
	}
}
void Ajustdown(HPDataType* a, int n,int parent)
{//O(N)
	assert(a);
	int child = 2 * parent+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 = child * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapCreate(HP* php, HPDataType* a, int n)
{
	assert(php);
	HPDataType*tmp=(HPDataType*)malloc(sizeof(HPDataType) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	memcpy(php->a, tmp, sizeof(HPDataType)*n);
	php->size = php->capacity = n;
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		Ajustdown(php->a, n, i);
	}
}
void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		int newcapacity=php->capacity == 0 ? 4 : 2 * php->capacity;
		HPDataType* tmp=(HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->size++] = x;
	Ajustup(php->a, php->size-1);
}
void HeapPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	Swap(&php->a[0], &php->a[php->size-1]);
	php->size--;
	Ajustdown(php->a, php->size-1 , 0);
}
HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	return php->a[0];
}
int HeapSize(HP* php)
{
	assert(php);
	return php->size;
}
bool HeapEmpty(HP* php)
{
	assert(php);
	if (php->size == 0)
		return true;
	else
		return false;
}

Test.c文件：

#include"Heap.h"
void test1()
{
	HP php;
	HeapInit(&php);
	HeapPush(&php, 75);
	HeapPush(&php, 56);
	HeapPush(&php, 30);
	HeapPush(&php, 25);
	//HeapPop(&php);
	int a=HeapSize(&php);
	printf("%d\n", a);
	HeapPrintf(&php);
	HeapPush(&php, 100);
	HeapPrintf(&php);
	HeapPop(&php);
	HeapPrintf(&php);
	HeapDestroy(&php);
}
int main()
{
	test1();
	//test2();
	//test3();
	//test4();
	return 0;
}

---