前言
在了解二叉堆之前，先来说一下优先队列。
优先队列是允许至少下列操作的数据结构：插入和删除最小者，它的工作是找出，返回，删除优先队列中的最小者。
要实现这种数据结构，除了二叉堆外还有许多方法。
1，使用一个链表存储这个序列，插入直接在表头或者表尾插入既可，时间复杂度为o(1)，删除最小元操作可以遍历链表，找到最小的元素，然后用链表的删除操作将其删除，时间复杂度为o(n)，这样做的弊端是如果我们要频繁地删除最小元，这个办法就相对来说不太好了。
2，使用二叉查找树存储这个序列，我们知道对二叉查找树的操作平均情况是o(logn)，这样无论是插入和删除都能以理想的时间去运行，但是我们删除操作并不是随机删除，我们每次都删除最小元，这样会导致左边的树的深度越来越小，树会越来越趋近于不平衡，那么使用二叉平衡树又如何呢，如果使用二叉平衡树，我们调整树的平衡会发生额外的开销，特别是二叉平衡树的删除操作，我在二叉平衡树(AVL树)的基本操作（c语言）这篇文章里面已经提到过了，二叉平衡树的删除操作开销很大。而我们最核心的操作就是删除最小元操作，用二叉平衡树也是不合理的。
我们将要使用的这种工具叫二叉堆，它可以仅用一个数组存储起来，不像树还要运用指针，它也已最坏情况o(logn)支持插入和删除最小元操作，除此之外，它还支持合并操作（虽然本文不会提到）。
二叉堆分为大根堆和小根堆，本文以小根堆的为例。
预备知识
完全二叉树：若设二叉树的深度为h，除第h 层外，其它各层 (1~h-1) 的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，这就是完全二叉树。下面是一颗完全二叉树。
观察这颗完全二叉树可以发现，完全二叉树是绝对平衡的，这样我们就彻底不用担心，插入和删除操作会影响树的平衡。其次，完全二叉树很有规律，我们可以只用一个数组去表示它，例如，上图可以用A,B,C,D,E,F,G,H,I,J来表示这颗树。
二叉堆的结构性：二叉堆有两个性质，结构性和堆序性。它的结构性是指堆是一颗完全二叉树，因此一个堆将由一个数组来存储。如下面所示，与上面的完全二叉树的图是对应的。该数组有一个0位置处有一个哨兵元素，哨兵元素（也称为哨兵节点）是一个特殊的元素或节点，用于简化边界条件、减少循环中的判断，从而提高代码效率。这里不详细说明，但是在堆排序（不会在本文提到）里面这个哨兵元素可以没有。
规律揭示：对于任意位置i上的元素，其左儿子在位置2i上，其右儿子在位置2i + 1上，它的父亲位置则在i / 2上（整数除法）。例如B结点的位置是2，它的左孩子就是4对应D，右孩子就是E，父亲结点就是1对应A。这个规律本文不会去证明，直接使用。
二叉堆的堆序性：二叉堆有两个性质，结构性和堆序性。我们以小根堆为例，它的堆序性是指，对于每一个节点X，X的父亲节点中的关键词小于或者等于X中的关键词，根节点除外，它没有父节点。与二叉查找树不同的是，它对一个节点的左孩子和右孩子之间的大小没有要求。下面就是一个例子。
只要满足二叉堆的两个性质，便是一个二叉堆。
定义
我们规定二叉堆里面存储的是整数值。
它有一个maxsize，用于表示这个堆的最大大小。
它还有一个size，用来表示这个堆的实际大小。
最后它还有一个整形数组arr，用来存储二叉堆。
二叉堆的初始化可以看下面的其他代码。
struct heap{
int maxsize;
int size;
int* arr;
};//by wqs
二叉堆的插入操作
首先规定如果已经有了待插入的元素，我们便什么都不做。
二叉堆的插入操作有2个步骤：
1，给二叉堆的实际大小加1，将待插入元素直接插入到二叉堆的最后面，这个时候堆很有可能二叉堆已经不满足堆序性。
2，我们下面的操作便是通过上滤操作，重新调整堆，上滤操作的定义是：新元素在堆中上滤直到找出正确的位置。主要是通过不断交换父节点和子节点来实现的，下面举个例子。
在上面这个例子中，我们要插入14，我们先size加1，并让14直接插入到二叉堆的最后面，也就是过程1，然后我们要不断比较14的父节点和14，如果14的父节点竟然比14大。说明14更应该为父节点，故交换14与父节点，如果最后14大于了父节点，说明已经满足了堆序性。我们比较14与它的父节点31,31>14，所以交换，到了过程2，接着我们比较14与它的父亲节点21，21>14，所以交换到了过程3，接着我们比较14和它的父亲节点13,13<14，所以调整完成，结束循环。这样来看二叉堆的插入还是很简单的，一个循环就可以解决。
下面是代码实现，接下来的这个函数接受一个已经创建好的堆p，以及一个要插入的数x，函数直接返回插入好的堆。
struct heap* insert(struct heap* p, int x){
int i;
for (i = ++p->size; p->arr[i / 2] > x; i = i / 2){//让i为初始化为最后一个元素，如果满足循环条件则一直更新父节点。
p->arr[i] = p->arr[i / 2];
}
p->arr[i] = x;//此时父节点小于待插入节点，直接插入x就可以满足堆序性。
return p;
}//by wqs
二叉堆的删除最小元操作
首先我们规定，如果原来的二叉堆中没有一个元素，我们便什么都不做。
二叉堆的删除最小元操作分为2个步骤：
1，让第一个节点等于最后一个节点，并且让size减1，这个时候二叉堆已经不满足堆序性。
2，然后通过下滤操作不断调整堆。至于下滤操作与上滤操作的区别就是调整的方向不一样，上滤是向上调整，而下滤是向下调整，由于我们在第一个节点就失去了堆序性，故要从上往下去调整。但是下滤调整有一个问题，一个节点有两个孩子，我们应该要与最小的孩子去比较，直到父节点比最小的孩子还小，我们才停止循环。
还是举一个例子，在下面这个例子中，我们要删除最小元，也就是13，对应下面第一个堆。
我们先让第一个节点13等下31这个节点，同时size减了1（少了一根线），这时已经失去了堆序性，对应上面第二个堆。
接下来31有两个孩子14和16，最小的孩子是14，发现31>14，所以交换31与14，就到了下面的第一个堆。
接着我们对比31与31的两个孩子19和21，较小的是19，我们交换31和19，得到了上面的第二个堆。
最后我们比较31的两个孩子65和26，较小的是26,31>26，所以我们交换31和26，得到了上面这个堆，31已经没有孩子节点了，所以我们的堆也调整完毕了，这样堆中删除了最小元13，并且重新满足了堆序性。可以看出删除操作也是比较简单。
下面是代码实现，接下来的函数接受一个已经创建好的堆p，函数直接返回删除最小元后的堆。
struct heap* deletemin(struct heap* p){
p->arr[1] = p->arr[p->size--];//让第一个等于最后一个，同时size减1
int i, child, temp;
for (i = 1; i * 2 <= p->size; i = child){//如果i * 2 > p->size，说明没有孩子，则不用接下来的调整，一定是满足堆序性
child = i * 2;//假设最小孩子是左孩子，如果假设不成立，则child++，变成右孩子。详情见下。
if (i * 2 != p->size && p->arr[child + 1] < p->arr[child]) child++;//防止数组越界，并找出最小孩子
if (p->arr[i] > p->arr[child]){//交换父节点和子节点
temp = p->arr[i];
p->arr[i] = p->arr[child];
p->arr[child] = temp;
}
else break;
}
return p;
}//by wqs
其他代码
堆的初始化操作
也就是定义它的maxsize,size,给arr分配空间。
struct heap* initial(int maxsize)
{
struct heap* p = (struct heap*)malloc(sizeof(struct heap));
p->maxsize = maxsize;
p->size = 0;
p->arr = (int*)malloc((maxsize + 1) * sizeof(int));
p->arr[0] = -1;
return p;
}//by wqs
判断一个序列是不是堆
int isheap(struct heap* p)
{
int i = 1;
for (i = 1; i <= p->size; i++)
{
if (2 * i <= p->size && p->arr[i] > p->arr[2 * i]) return 0;
if (2 * i + 1 <= p->size && p->arr[i] > p->arr[2 * i + 1]) return 0;
}
return 1;
}//by wqs
打印堆的遍历结果
void jiegou(struct heap* p)
{
int i = 1;
printf("堆的遍历结果为");
for (i = 1; i <= p->size; i++)
{
printf("%d ", p->arr[i]);
}
printf("\n");
}//by wqs
总代码
#include<stdio.h>
#include<stdlib.h>
struct heap {
int maxsize;
int size;
int* arr;
};
struct heap* initial(int);
int isheap(struct heap*);
struct heap* insert(struct heap*, int);
struct heap* deletemin(struct heap*);
void jiegou(struct heap*);
int main()
{
int maxsize, i = 1, x;
printf("输入堆的最大空间:");
scanf("%d", &maxsize);
struct heap* p = initial(maxsize);
printf("堆初始化成功\n");
int size;
printf("请输入堆的元素个数:");
scanf("%d", &size);
printf("请依次输入堆序列:\n");
for (i = 1; i <= size; i++)
{
scanf("%d", &p->arr[i]);
p->size++;
}
jiegou(p);
if (isheap(p) == 0)
{
printf("不是堆\n");
return 0;
}
else printf("这是堆\n");
printf("接下来进入操作集\n输入1插入，输入2删除，输入3免费打印一次堆的结构，输入0退出");
while (1) {
int key;
printf("输入:");
scanf("%d", &key);
if (key == 0) break;
else if (key == 1) {
printf("插入:");
scanf("%d", &x);
p = insert(p, x);
printf("插入成功\n");
}
else if (key == 2) {
p = deletemin(p);
printf("删除最小元成功\n");
}
else if (key == 3) {
jiegou(p);
}
else printf("你的输入有误");
}
return 0;
}
struct heap* initial(int maxsize)
{
struct heap* p = (struct heap*)malloc(sizeof(struct heap));
p->maxsize = maxsize;
p->size = 0;
p->arr = (int*)malloc((maxsize + 1) * sizeof(int));
p->arr[0] = -1;
return p;
}
int isheap(struct heap* p)
{
int i = 1;
for (i = 1; i <= p->size; i++)
{
if (2 * i <= p->size && p->arr[i] > p->arr[2 * i]) return 0;
if (2 * i + 1 <= p->size && p->arr[i] > p->arr[2 * i + 1]) return 0;
}
return 1;
}
struct heap* insert(struct heap* p, int x) {
int i;
for (i = ++p->size; p->arr[i / 2] > x; i = i / 2) {
p->arr[i] = p->arr[i / 2];
}
p->arr[i] = x;
return p;
}
struct heap* deletemin(struct heap* p) {
p->arr[1] = p->arr[p->size--];
int i, child, temp;
for (i = 1; i * 2 <= p->size; i = child) {
child = i * 2;
if (i * 2 != p->size && p->arr[child + 1] < p->arr[child]) child++;
if (p->arr[i] > p->arr[child]) {
temp = p->arr[i];
p->arr[i] = p->arr[child];
p->arr[child] = temp;
}
else break;
}
return p;
}
void jiegou(struct heap* p)
{
int i = 1;
printf("堆的遍历结果为");
for (i = 1; i <= p->size; i++)
{
printf("%d ", p->arr[i]);
}
printf("\n");
}//by wqs
效果展示
给你一个免费的二叉堆，其他输入自行发挥。
11
13 14 16 19 21 19 68 65 26 32 31