学步园

堆排序，基于最大堆的堆排序。

摘自：http://blog.sina.com.cn/s/blog_5115d58c0100vr26.html

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cassert>
#include <vector>
#include <algorithm>

using namespace std;

//int a[N]; n = N
void print(int* a,int n)
{
    assert( a != NULL && n > 0);
    for(int i = 0; i < n; ++i)
    {
        printf("%2d ",a[i]);
    }
    printf("\n");
}

void swap(int& a,int& b)
{
    int t = a;
    a = b;
    b = t;
}

//int a[N];heap_size = N
void max_heapify(int* a,int i,int heap_size)
{
    assert( a != NULL );
    assert( i >= 0 && i < heap_size );

    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int largest = -1;
    //printf("max_heapify\n");
    //printf("%d-%d-%d\n\n",i,2 * i + 1,2 * i + 2);

    if ( left < heap_size )
    {
        if ( a[left] > a[i] )
            largest = left;
    }
    else
    {
        largest = -1;
    }

    if ( right < heap_size /*&& a[right] > a[largest]*/ )
    {
        if ( a[right] > a[largest] )
            largest = right;
    }
    else
    {
        largest = -1;
    }

    if ( i != largest && largest != -1)
    {
        swap( a[i],a[largest] );
        max_heapify(a,largest,heap_size);
    }
}

//int a[N];n = N,heap_size = N
void build_max_heap(int* a,int n,int heap_size)
{
    //printf("build_max_heap\n");
    for( int node = n / 2 -1; node >= 0; --node )
    {
        //printf("for:a[%d]\n",node);
        max_heapify(a,node,heap_size);
    }
}

void heap_sort(int* a,int n,int heap_size)
{
    build_max_heap(a,n,heap_size);
    for(int index = n - 1; index >= 1;--index)
    {
        swap(a[index],a[0]);

        heap_size = heap_size - 1;
        max_heapify(a,0,heap_size);
    }
}

void print_ele(int& a)
{
    printf("%2d ",a);
}

int main()
{
    int a[] = {63,72,10,24,10,89,56,40,17,68};
    const int ARRAY_SIZE = sizeof(a)/sizeof(*a);

    //use my
    //
    build_max_heap(a,ARRAY_SIZE,ARRAY_SIZE);
    cout << "\nmy build heap:" << endl;
    print(a,ARRAY_SIZE);

    heap_sort(a,ARRAY_SIZE,ARRAY_SIZE);
    cout << "\nmy heap sort:" << endl;
    print(a,ARRAY_SIZE);

    //use STL
    //
    vector<int> v(a,a+ARRAY_SIZE);
    make_heap( v.begin(),v.end() );
    cout << "\nuse STL make_heap:" << endl;
    for_each(v.begin(),v.end(),print_ele);

    sort_heap( v.begin(),v.end() );
    cout << "\n\nuse STL sort_heap:" << endl;
    for_each(v.begin(),v.end(),print_ele);

    cout << endl;
    return 0;
}