堆：
- 此处堆为二叉树的应用，不是计算机中用于管理动态内存的堆。
- 形状是完全二叉树。
- 堆分两种：最大堆，最小堆。
- 最大堆：每个节点比子树所有节点的数值都大，根节点为最大值。
- 最小堆：每个节点比子树所有节点的数值都小，根节点为最小值。
- 左右节点的数值没有顺序要求，但有左子节点才能有右子节点。
- 一般用数组实现堆。最小堆可以实现优先队列。
注：完全二叉树：每个节点最多2个节点，倒数第二层级（含）之前层级的所有节点都有元素，最后一层级从左到右依次有元素（中间不能断）。
子树：节点及其所有子节点形成子树。（即节点，左右子节点，左右子节点的左右子节点，。。。）
根节点：没有父节点。
兄弟节点：其父节点是同一个节点。
| 节点 | 索引号（根节点为0） |
|---|---|
| 节点 | x |
| 父节点 | （x-1）// 2 |
| 左兄弟节点（右节点才有） | x - 1 |
| 右兄弟节点（左节点才有） | x + 1 |
| 左子节点 | 2x + 1 |
| 右子节点 | 2x + 2 |
C语言实现：（使用数组实现最小堆）
创建堆（结构体数据类型）：记录数组地址和元素个数
// 堆（结构体数据类型）
typedef struct Heap
{
int *p; // 记录数组地址
int n; // 记录元素个数
} Heap; // 别名（函数）堆初始化：
// 堆初始化
void init(Heap *heap, int length)
{
heap->p = (int *)malloc(length * sizeof(int)); // 分配内存空间
if(heap->p == NULL)
{
perror("Memory allocation failed");
exit(-1);
}
heap->n = 0; // 元素个数，初始化为0
}创建堆变量，并初始化
Heap heap; // 创建堆变量
init(&heap, 8); // 设置数组最大元素个数为8添加元素：
1、先在末尾添加元素。
2、（向上调整）与父节点比较大小，若小于父节点，与父节点交换位置，直到开头位置（根节点，数组第一个元素）。
（注：子节点索引号为x，父节点索引号为(x-1)//2）
void add(Heap *heap, int data) // add a element to the heap
{
// 往末尾添加元素
heap->p[heap->n] = data;
// (向上调整) 与父节点比较，小于父节点的值，与父节点交换位置
int cur = heap->n;
while(cur > 0)
{
int parent = ceil((cur - 1) / 2);
if(heap->p[parent] > data)
{
heap->p[cur] = heap->p[parent];
heap->p[parent] = data;
cur = parent;
}
else break;
}
// 每添加一个元素，元素个数+1
heap->n++;
}删除（根节点）：
1、记录根节点（数组第一个元素）和末尾节点（数组最后一个元素）。
2、末尾节点的值换到根节点位置，元素个数-1。
3、（向下调整）从根节点开始，依次与左右子节点比较大小，数值小的是父节点，直到比对到末尾。
（注：父节点索引号为x，左子节点索引号为2x+1，右子节点索引号为2x+2）
int delete(Heap *heap) // delete root from the heap
{
if(heap->n == 0) return -1; // 空树
heap->n--; // 每删除一次根节点，元素个数-1
int root = heap->p[0], enddata = heap->p[heap->n];
heap->p[0] = enddata; // 末尾元素换到第一个位置
// (向下调整) 与左右子节点比较，若子节点小，与较小子节点交换位置
int cur = 0;
while(cur <= heap->n)
{
int left = cur * 2 + 1, right = cur * 2 + 2, minchild;
if(left > heap->n) break; // 没有左子节点
if(right > heap->n) minchild = left; // 没有右子节点，有左子节点
else // 左右子节点都有的情况
{
// 左右子节点比较，找到较小子节点
if(heap->p[right] < heap->p[left]) minchild = right;
else minchild = left;
// 父节点与较小子节点比较，若子节点小，与子节点交换位置
if(heap->p[minchild] < enddata)
{
heap->p[cur] = heap->p[minchild];
heap->p[minchild] = enddata;
cur = minchild;
}
else break;
}
}
return root;
}获取根节点：（数组第一个元素）
int getroot(Heap *heap) // get the root from the heap
{
if(heap->n == 0)
{
printf("Empty heap\n");
exit(-1);
}
return heap->p[0];
}遍历堆：（类似广度遍历二叉树）
每个节点比子树的所有节点都小，但左右节点没有顺序要求。
void traverse(Heap *heap) // show element one by one (like breadth traverse the tree)
{
if(heap->n == 0) return ;
printf("elements(%d): ", heap->n);
for(int k = 0; k < heap->n; k++)
{
printf("%d ", heap->p[k]);
}
printf("\n");
}清空堆：
释放数组内存空间，指向数组的指针指向NULL，元素个数为0。
void clear(Heap *heap) // clear the heap (free memory space of the array)
{
free(heap->p); // 释放数组内存空间
heap->p = NULL; // 指针指向NULL，避免野指针
heap->n = 0; // 元素个数为0
}
完整代码：（heap.c）
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
/* structure */
typedef struct Heap
{
int *p; // memory address of the heap (array)
int n; // the number of the heap
} Heap;
/* function prototype */
void init(Heap *, int); // heap initialization
void add(Heap *, int); // add a element to the heap
int delete(Heap *); // delete root from the heap
int getroot(Heap *); // get the root from the heap
void traverse(Heap *); // show element one by one (likely breadth traverse the tree)
void clear(Heap *); // clear the heap (free memory space of the array)
/* main function */
int main(void)
{
Heap heap;
init(&heap, 8);
printf("length: %d\n", heap.n);
add(&heap, 5);
printf("root(the minimum): %d\n", getroot(&heap));
traverse(&heap);
add(&heap, 8);
add(&heap, 3);
add(&heap, 9);
add(&heap, 2);
printf("root(the minimum): %d\n", getroot(&heap));
traverse(&heap);
delete(&heap);
printf("root(the minimum): %d\n", getroot(&heap));
traverse(&heap);
delete(&heap);
printf("root(the minimum): %d\n", getroot(&heap));
traverse(&heap);
clear(&heap);
printf("length: %d\n", heap.n);
printf("root(the minimum): %d\n", getroot(&heap));
return 0;
}
/* subfunction */
void init(Heap *heap, int length) // heap initialization
{
heap->p = (int *)malloc(length * sizeof(int));
if(heap->p == NULL)
{
perror("Memory allocation failed");
exit(-1);
}
heap->n = 0;
}
void add(Heap *heap, int data) // add a element to the heap
{
// add a element to the end of the heap
heap->p[heap->n] = data;
// (adjust up) compair with parent,if smaller than parent, change the position
int cur = heap->n;
while(cur > 0)
{
int parent = ceil((cur - 1) / 2);
if(heap->p[parent] > data)
{
heap->p[cur] = heap->p[parent];
heap->p[parent] = data;
cur = parent;
}
else break;
}
heap->n++;
}
int delete(Heap *heap) // delete root from the heap
{
if(heap->n == 0) return -1;
heap->n--;
int root = heap->p[0], enddata = heap->p[heap->n];
heap->p[0] = enddata; // put the last element to the first position
// (adjust down) compair with left and right child, minimun is parent
int cur = 0;
while(cur <= heap->n)
{
int left = cur * 2 + 1, right = cur * 2 + 2, minchild;
if(left > heap->n) break; // no left child
if(right > heap->n) minchild = left; // have left child, no right child
else // have left child and right child
{
// compair left child and right child, find smaller one
if(heap->p[right] < heap->p[left]) minchild = right;
else minchild = left;
// smaller child compair with parent,if child is the smallest, change
if(heap->p[minchild] < enddata)
{
heap->p[cur] = heap->p[minchild];
heap->p[minchild] = enddata;
cur = minchild;
}
else break;
}
}
return root;
}
int getroot(Heap *heap) // get the root from the heap
{
if(heap->n == 0)
{
printf("Empty heap\n");
exit(-1);
}
return heap->p[0];
}
void traverse(Heap *heap) // show element one by one (like breadth traverse the tree)
{
if(heap->n == 0) return ;
printf("elements(%d): ", heap->n);
for(int k = 0; k < heap->n; k++)
{
printf("%d ", heap->p[k]);
}
printf("\n");
}
void clear(Heap *heap) // clear the heap (free memory space of the array)
{
free(heap->p);
heap->p = NULL;
heap->n = 0;
}编译链接： gcc -o heap heap.c
执行可执行文件： ./heap
