比如：3 27 36 27
如果堆頂3先輸出，則，第三層的27（最后一個(gè)27）跑到堆頂，然后堆穩(wěn)定，繼續(xù)輸出堆頂，是剛才那個(gè)27，這樣說(shuō)明后面的27先于第二個(gè)位置的27輸出，不穩(wěn)定。
#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);
}
}