堆排序

为了理解思想，其简单实现如下：

#include
using namespace std;

//ÒÑintΪÀý ×î´ó¶Ñ
void make_heap(int a[], int size)
{
}
int heap_push(int a[], int n, int data)
{
    int i ;
    while ( n >= 1 ) {
        i = (n-1)/2;
        if (a[i] > data) break;
        a[n] = a[i];
        n = i;
    }
    a[n] = data;
    return n;
}

int heap_pop(int a[], int n)
{
    if (n==0) {
        return a[n];
    }
    int ret = a[0];
    int i = 0;
    int max = 2*i+1;
    while ( max <= n) {
        if ( max + 1 <= n ) {
            max = a[max] > a[max+1]?max:max+1;
        }
        if (a[max] <= a[n]) break;
        a[i] = a[max];
        i = max;
        max = 2*i+1;
    }
    a[i] = a[n];
    return ret;
}

void output(int a[], int n){
    for (int i=0; i        cout<    }
    cout<}
void heap_sort(int a[], int n)
{
    //build
    for (int i=0; i        heap_push(a, i, a[i]);
    }
    //sort
    for (int i=n-1; i>0; i--) {
        a[i] = heap_pop(a,i);
    }
}

int main(int argc, char **argv)
{
    int a[]={1, 100, 5, 2, 10, 11, 18, 90};

    int n = sizeof(a)/sizeof(int);
 
    heap_sort(a, n);

    for (int i=0; i        cout<    }   
    cout<
    return 0;
}