堆是一棵完全二叉树，之所以需要堆，是因为我们需要堆序性，堆的父节点都大于或小于其子节点，这样的有序性能让我们快速找到最大值或最小值，即根节点，时间复杂度是O（1）
由于完全二叉树的特殊性，我们可以使用数组表示一棵完全二叉树，而不是链表，这样做能获得最大的索引效率，缺点是树的大小不能动态增长
对于简单的需求，数组实现的堆可以达到最佳效率：
堆结构体：
typedef struct heap { int current_size; int max_size; char *h; } heap_t;
堆的实现很简单，一个数组h，数组的大小max_size，以及当前已使用的大小current_size
初始化堆：
int init_heap(heap_t *heap, int size) { if (size <= 0) size = 8; heap = (heap_t *)malloc(sizeof(heap_t) + size * sizeof(char)); if (!heap) return -1; heap->h = heap++; heap->current_size = 0; heap->max_size = size; heap->h[0] = '0'; // 占用数组第一个位置0，便于insert和delete函数的索引 return 0; }
初始化一个堆，就是为堆结构体对象和其数组成员申请空间
需要留意的是数组第一个位置0是不用做存储节点的，原因是0用作索引计算起来不方便，后面会介绍
现在已经有了一个空堆，我们可以做的无非两种操作：
1.向堆中添加一个节点
2.从堆中取出一个节点（根节点）
由于随意添加和删除节点会破坏堆的性质，也就是堆序性，因此在插入和删除操作时，我们要确保操作完成后，堆的性质不变
1.插入
应该从哪里插入呢？由于插入一个节点后数组会多出一个元素（插入前为空位），因此我们采用类似冒泡的方法，将这个空位上滤，所有大于待插入节点的父节点都会被下滤，最后我们得到的空位就是待插入节点正确的位置：
void insert(heap_t *heap, char c) { // 上滤，插入一个节点 if (if_full(heap)) { printf("heap is full !\n"); return; } int i; // 根据大小遍历交换空位与其父节点 for (i = ++heap->current_size; heap->h[i] > c; i /= 2) heap->h[i] = heap->h[i/2]; heap->h[i] = c; // 此时的 i 大于其父节点，小于其所有子节点 heap->current_size++; }
需要复习的是，对于完全二叉树的一个节点i，其父节点为2i，左子节点为 i / 2，右子节点为（i / 2）+ 1
2.删除根节点
删除根节点也就是取出最大(小)值节点，由于删除后数组少了一个元素，而且是第一个元素，需要一个新的最小值节点 作为根节点。同时要将最后一个元素更换位置，以确保完全二叉树的形式
char delete_min(heap_t *heap) { if (is_empty(heap)) { printf("heap is empty !\n"); return heap->h[0]; } int i, child; char min, last; min = heap->h[1]; last = heap->h[heap->current_size--]; for (i = 1; i * 2 <= heap->current_size; i = child) { // 找出较小的子节点 child = i * 2; // 左子节点 if (child != heap->current_size && heap->h[child+1] < heap->h[child]) child ++; // 右子节点 if (last > heap->h[child]) heap->h[i] = heap->h[child]; // 交换父子节点，父节点是一个空位 else break; // 子节点大于last节点 } heap->h[i] = last; // 退出循环的两种情况：1. i的子节点是叶子节点 2. i的子节点大于最后一个节点last return min; }
