//来自http://www.blogjava.net/dreamingnest/archive/2008/10/06/232668.html
#include<iostream>
#include<algorithm>
using namespace std;
int A[11],heap_size;
void MaxHeapify(int A[],int i)
{
    int largest=-1;
    int left=2*i;//获取根节点的左孩子
    int right=2*i+1;//获取根节点的右孩子
    if(left<=heap_size&&A[left]>A[i])
        largest=left;
    else
        largest=i;
    if(right<=heap_size&&A[right]>A[largest])
        largest=right;
    if(largest!=i)//根节点不是最大值则交换后继续递归
    {
        swap(A[i],A[largest]);
        MaxHeapify(A,largest);
    }
}
void BuildMaxHeap(int A[])
{
    for(int i=10/2;i>=1;i--)
        MaxHeapify(A,i);
}
int main()
{
    int i;
    heap_size=10;
    for(i=1;i<11;i++)
        cin>>A[i];
    BuildMaxHeap(A);
    cout<<"建立的最大堆为：";
    for(i=1;i<11;i++)
        cout<<A[i]<<"-";
    cout<<endl;
    for(i=10;i>1;i--)
    {
        swap(A[i],A[1]);
        heap_size--;
        MaxHeapify(A,1);
    }
    cout<<"排序后的结果为：";
    for(i=1;i<11;i++)
        cout<<A[i]<<" ";
    cout<<endl;
    return 0;
}
//来自http://blog.csdn.net/Tuzki/archive/2008/10/08/3032175.aspx

#include <iostream>

#include <ctime>

using namespace std;

 

// 注意父子的计算方式。节点编号从0开始。

inline int parent(const int x) { return ((x-1)/2); }

inline int left(const int x) { return (2*x+1); }

inline int right(const int x) { return (2*x+2); }

 

int cmp = 0;    // 总共执行比较操作的次数

int swp = 0;    // 总共执行交换操作的次数

 

// 调整以i为根的子树，使之成为最大堆，size为堆的大小

void maxHeapify(int a[], int size, int i)

{

    cmp +=2;

    swp++;

 

    int l = left(i);

    int r = right(i);

    int largest = i;    // 最大堆的根

   

    if( (l < size) && (a[l] > a[i]) )        largest = l;

    if( (r < size) && (a[r] > a[largest]) )  largest = r;

    if( largest != i )

    {

        swap(a[i], a[largest]);         // 三个节点中较大者成为根

        maxHeapify(a, size, largest);   // 可能破坏了堆性质，重新调整

    }

}

 

void buildMaxHeap(int a[], int size)    // 建堆

{

    for(int i = (size-1)/2; i>=0; i--)

    {

        maxHeapify(a, size, i);

    }

}

 

void heapSort(int a[], int size)        // 堆排序，(n-1)*O(lgn) = O(nlgn)

{

    swp++;

 

    buildMaxHeap(a, size);

    for(int i=size-1; i>0; i--)         // 重复n-1次

    {

        swap(a[0], a[i]);

        size--;

        maxHeapify(a, size, 0);         // 每次调整，花费为O(lgn)

    }

}

 

int main()

{

    int a[] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};

 

    heapSort(a, sizeof(a)/sizeof(a[0]));

 

    cout << "总共进行比较 " << cmp << " 次，总共进行交换 " << swp << " 次" << endl;

 

    for(int i=0; i<sizeof(a)/sizeof(a[0]); i++)

    {

        cout << a[i] << " ";

    }

    cout << endl;

 

    return 0;

}