堆总是一棵完全二叉树。
1. 满二叉树 ：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是 说，如果一个二叉树的层数为 K ，且结点总数是 ，则它就是满二叉树。 2. 完全二叉树 ：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为 K 的，有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 K 的满二叉树中编号从 1 至 n 的结点一一对 应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。则我们可以根据定义得出，一个二叉树可以由一维数组转换而成——
下面我们创建一个简单的一维数组，将其转换为一个完全二叉树
由上图可知，这个二叉树是无序的，并且没有什么规律与特点。这时候我们就出现了堆这种数据结构——它分为小堆与大堆，可以将所有数据最小的和最大的数据挑选出来，让二叉树变得有序。
我们来看看由上叙数组所建成的小堆与大堆——
小堆：
大堆：
现在我们已经了解了堆的结构，下面我们来建堆和调堆——
一、堆的功能：我们需要定义一个数组来存放数据，并且还得知道数据多少。这时我们类比建栈的方式建立一个结构体，存放数组和知道数组大小，并且我们还需要判断数组是否装满来考虑扩容及删除——
分装头文件，明确堆需要
#define _CRT_SECURE_NO_WARNINGS #include#include #include #include typedef int HeapData; typedef struct Heap { HeapData* a; int size; int capacity; }Heap; //堆的初始化 void HeapInit(Heap* ph); //堆的销毁 void HeapDestory(Heap* ph); //堆的数据插入 void HeapPush(Heap* ph, HeapData x); //堆的数据删除 void HeapPop(Heap* ph); //堆的数据判空 bool HeapEmpty(Heap* ph); //堆的大小 int HeapSize(Heap* ph); //堆顶数据 HeapData HeapTop(Heap* ph); //堆数据的打印 void HeapPrint(Heap* ph);
这里我们重命名"int"为我测试所用的数据类型，可以让后期需要更改数据类型时方便很多——
二、堆的初始化：void HeapInit(Heap* ph)
{
assert(ph);
ph->a = NULL;
ph->capacity = ph->size = 0;
}
三、堆的销毁：
void HeapDestory(Heap* ph)
{
assert(ph);
free(ph->a);
ph->a = NULL;
ph->capacity = ph->size = 0;
}
四、堆的数据插入与删除：
1、数据的交换——
插入与删除必定用到数据交换，这里我们可以分装出来
void Swap(HeapData* p1, HeapData* p2)
{
HeapData tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
2、插入
这里插入数据前数组经过初始化为NULL，且大小也为0。我们需要在插入时进行判空处理，若为NULL，则需要申请为数组开辟空间——
void HeapPush(Heap* ph, HeapData x)
{
assert(ph);
if (ph->capacity == ph->size)
{
int newcapacity = ph->capacity == 0 ? 4 : ph->capacity * 2;
HeapData* tmp= (HeapData*)realloc(ph->a, sizeof(HeapData) * newcapacity);
if (tmp == NULL)
{
perror("HeapPush realloc");
exit(-1);
}
ph->a = tmp;
ph->capacity = newcapacity;
}
ph->a[ph->size] = x;
ph->size++;
AdjustUp(ph->a, ph->size-1);
//AdjustDwon(ph->a, ph->size - 1, 0);//不可用这里，向下调整充要条件是左右子树都为大堆/小堆，这里建堆不满足
}
这里在开辟好空间存入数据后需要进行调堆处理，我们这里有两种方式——向上调整和向下调整。但是我们这里只能进行向上调整，因为向下调整的充要条件是除开“根”的数据以外，左右子树必须也为大堆或者小堆（下面我们会解释原因）。
这里用到向上调整数据——我们将插入数据依次与其“父亲“进行比较，若创建小堆，则如下图所示，一直与“父亲”比较，直至不再满足”孩子“小于”父亲“而停止。
void AdjustUp(HeapData* a, int child)
{
int parent = (child - 1) / 2;
while(parent>=0)
//while (child > 0)
//这里用这个更好，用parent判断则需考虑下方a[child]!=a[parent]
{
if (a[child] < a[parent])//写小堆
//if (a[child] > a[parent])//写大堆
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
3、堆的数据删除：
这里需要用到一个十分巧妙的思维，需要将其根的数据与末尾数据进行调换然后再调整删除——
void HeapPop(Heap* ph)
{
assert(ph);
assert(ph->size > 0);
Swap(&ph->a[0], &ph->a[ph->size - 1]);
ph->size--;
AdjustDwon(ph->a, ph->size, 0);
}
这里我们将用到向下调整，与向上调整不同的是，这里我们要先找出父辈左右孩子中较小（较大）的数据与其父辈进行比较，这里以建小堆为例，同向上调整相同，我们可以类比而出———
void AdjustDwon(HeapData* a, int size, int parent)
{
int child = parent * 2 + 1;
while (child < size)
{
//if (child + 1 < size && a[child] > a[child + 1])//大堆
if (child + 1 < size && a[child] < a[child + 1])//小堆
{
child++;
}
if (a[child] > a[parent])//写小堆
//if (a[child] < a[parent])//大堆
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
五、堆的判空
因为bool非真即假，则我们可以直接返回判断结果
bool HeapEmpty(Heap* ph)
{
assert(ph);
return ph->size == 0;
}
六、堆存储数据大小
int HeapSize(Heap* ph)
{
assert(ph);
return ph->size;
}
七、堆顶数据
HeapData HeapTop(Heap* ph)
{
assert(ph);
return ph->a[0];
}
八、堆的数据打印
void HeapPrint(Heap* ph)
{
assert(ph);
for (int i = 0; i < ph->size; i++)
{
printf("%d ", ph->a[i]);
}
printf("n");
}
