比如：3 27 36 27
如果堆顶3先输出，则，第三层的27（最后一个27）跑到堆顶，然后堆稳定，继续输出堆顶，是刚才那个27，这样说明后面的27先于第二个位置的27输出，不稳定。
#define LEFT(i) (((i)<<1)+1)
#define RIGHT(i) (((i)+1)<<1)
#define PARENT(i) (((i)-1)>>1)
void
min_heapify(int index, int *heap, int heap_size) //precondition: LEFT(index) and RIGHT(index) are both already min-heap
{
int min = index;
if(LEFT(index)<heap_size && heap[LEFT(index)]<heap[min])
min = LEFT(index);
if(RIGHT(index)<heap_size && heap[RIGHT(index)]<heap[min])
min = RIGHT(index);
if(min != index) {
swap(heap+min, heap+index);
min_heapify(min, heap, heap_size);
}
}
void
build_heap(int *heap, int heap_size)
{
int i = (heap_size>>1);
for( ; i>=0; --i)
min_heapify(i, heap, heap_size);
}
void
heap_sort(int *heap, int heap_size)
{
build_heap(heap, heap_size);
while(heap_size > 1) {
swap(heap, heap+heap_size-1);
--heap_size;
min_heapify(0, heap, heap_size);
}
}