static ? void ?_build_heap( int ? * array, int ?len);
static ? void ?_adjust_heap( int ? * array, int ?idx, int ?len);

int ?heap_sort( int ? * array, int ?begin, int ?end)
{
???? if (array == NULL || begin > end)? return ? 0 ;

???? // 自此以后，index從1開始。
????array -- ;
???? int ?len? = ?end - begin + 1 ;
????_build_heap(array,len);

???? int ?tmp;
???? int ?i;

???? for (i = 1 ;i < len; ++ i){
????????tmp? = ?array[len - i + 1 ];
????????array[len - i + 1 ]? = ?array[ 1 ];
????????array[ 1 ]? = ?tmp;
????????_adjust_heap(array, 1 ,len - i);
????}
}

// input:?任意數組?output:大頂堆
static ? void ?_build_heap( int ? * array, int ?len)
{
??? int ?i;
??? for (i = len / 2 ;i >= 1 ; -- i){
????????_adjust_heap(array,i,len);
???}
}

// 使重新使array滿足堆特性
static ? void ?_adjust_heap( int ? * array, int ?idx, int ?len)
{
???? int ?left;
???? int ?right;
???? int ?larger? = ?idx;
???? int ?tmp? = ?array[idx];

????left? = ?(idx << 1 );
????right? = ?left + 1 ;

???? while (?left <= ?len){
???????? if (right <= len && array[right] > array[left]){
????????????larger? = ?right;?
????????} else {
????????????larger? = ?left;
????????}

???????? if (?array[larger] > tmp?){
????????????array[idx]? = ?array[larger];
????????????idx? = ?larger;
????????????left? = ?(idx << 1 );
????????????right? = ?left + 1 ;
????????} else {
???????????? break ;
????????}
????}

????array[idx]? = ?tmp;
}