A Za, A Za, Fighting...

比如：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);
    }
}