优先队列——二叉堆实现
二叉堆是完全二叉树
二叉堆满足堆特性：父节点键值（https://zh.wikipedia.org/w/index.php?title=键值&action=edit&redlink=1 "键值（页面不存在）")总是大于等于（https://zh.wikipedia.org/w/index.php?title=键值&action=edit&redlink=1 "键值（页面不存在）")其任一子节点的键值，并且每个节点的左右子树各自独立构成一个二叉堆（都是最大堆 https://zh.wikipedia.org/wiki/最大堆 "最大堆"或最小堆 https://zh.wikipedia.org/wiki/最小堆 "最小堆")）。
当父节点的数值总是大于或等于其任何一个子节点的数值时称为最大堆 。 当父节点的数值总是小于或等于任何一个子节点的数值时称为最小堆
因为完全二叉树的特性, 父节点和子节点的关系是
i
/ \
2i 2i+1
所以完全二叉树可以直接用数组表示(如图):
那么二叉堆这种有序队列如何入队呢？
在上图所示的最小堆结构中插入一个键值为2的元素，在数组末尾加入这个元素后，并尽可能地将该元素向上移动至父节点位置。具体而言，在父节点满足键值不大于子节点键值的特点时，则会继续向上移动；直到无法再进行移动为止。由此可见，二叉堆插入操作的时间复杂度具有Ο(logn)这一特性。
那如何出队呢？如图：
出队操作必然是出队列表的第一个元素（即最小元素），因此该位置成为空缺。我们需要对父节点进行重新排列，在此过程中从父节点两个子节点中选择较小的那个并将其向上移动到父节点的位置上。此时原来的那个子节点则成为新的父节点，并且该位置空置起来的状态实际上涉及对子堆结构进行调整。如此反复递归上移直至被移出的叶子节点。然后将数组末尾元素填入该空缺处
有些人可能有疑问。
当出队操作发生时, 会立即从队列中取出最顶端节点。
主动维护调整顺序的过程并不复杂。
那么为什么不只取前面的节点呢？
答案即为：为了确保之后维护仍然是一个完整的二叉结构。基于完全二叉结构的特点，在不成为满的完整结构的前提下...
需要注意的是，在构建完全二叉树时，若未将最后一个元素取出，则可能导致完全二叉树的叶子层节点无法保持顺序排列。
最后出队+维护操作的时间复杂度也是O(1)+Ο(logn)。
代码
typedef struct heap HEAP;
struct heap
{
int arr[127];
int size;
};
void insert(HEAP *h, int n)
{
int sz = h->size++;
printf( "%d --- %d\n", sz , n );
while( sz > 0 )
{
if( n < h->arr[(sz-1)/2] )
{
h->arr[sz] = h->arr[(sz-1)/2];
sz = (sz-1) / 2;
}
else
{
h->arr[sz] = n;
return;
}
}
h->arr[0] = n;
}
void delete( HEAP *h )
{
int i;
int tmp;
int head = h->arr[0];
h->size--;
h->arr[0] = h->arr[h->size];
h->arr[h->size] = 0;
i = 1;
while( h->arr[i]>0 )
{
if( h->arr[i] < head )
{
h->arr[(i-1)/2] = h->arr[i];
h->arr[i] = head;
i = i*2 + 1;
}
else if( h->arr[i+1] < head )
{
h->arr[(i-1)/2] = h->arr[i+1];
h->arr[i+1] = head;
i = 2*(i+1)+1;
}
else
{
return;
}
}
}