//堆排序
#include <stdio.h>
#include <iostream>

void heap_sort(int*, int);    //堆排序算法
void build_max_heap(int*, int);    //建立最大堆
void max_heapify(int*, int, int);    //将插入的结点保持最大堆

int main()
{
    int i, j;
    int sort[11] = {0, 6, 5, 4, 9, 3, 0, 8, 2, 1, 7};    //数组0下标丢弃不用
    int length = sizeof(sort) / sizeof(int) - 1;
    heap_sort(sort, length);
    for(i = 1; i<= length; i++){
        printf("%d\n",sort[i]);
    }
    system("pause");
    return 0;
}

//先调用建立最大堆算法,将堆建立为一个最大堆
//然后将根结点与最后一个结点互换
//调用最大堆保持算法,保持堆为一个最大堆
//循环length-1次后,排序结束
//算法复杂度为length*lg(length)
void heap_sort(int* ptr, int length)
{
    int i, temp;
    build_max_heap(ptr, length);
    for(i = length; i >= 2; i--){
        temp = ptr[i];
        ptr[i] = ptr[1];
        ptr[1] = temp;
        length--;
        max_heapify(ptr, length, 1);
    }
}

void build_max_heap(int* ptr, int length)
{
    int i;
    for(i = length / 2; i >= 1; i--){
        max_heapify(ptr, length, i);
    }
}

void max_heapify(int* ptr, int length, int i)
{
    int lar, temp;
    int l = i * 2;
    int r = i * 2 + 1;
    if((l <= length) && (ptr[l] > ptr [i])) lar = l; else lar = i;
    if((r <= length) && (ptr[r] > ptr [lar]))  lar = r;
    if(lar != i){
        temp = ptr[i];
        ptr[i] = ptr[lar];
        ptr[lar] = temp;
        max_heapify(ptr, length, lar);
    }
}