堆排序

要实现堆排序首先要理解堆相关的一些重要概念。
    （1）什么是堆，堆于优先队列的关系？
    堆实际上是优先队列数据结构的实现，也可以说，堆是具有优先队列性质的容器实现。
    优先队列是允许下面两个操作的数据结构：
Insert
DeleteMin
    即    DeleteMin <----[优先队列] <----Insert
    尤其要强调的是DeleteMin的操作，这步操作目的是找到，返回，或删除最小项。切记！不仅仅是简单的出队，是做了一系列换位后将最小元素置换出来。
    提供了类似这样的deleteMin操作和Insert操作的即是优先队列的实现。
    比如最容易想到的两种实现方式为：
    [1] 以一个链表来实现，这样Insert操作很容易为O(1), deleteMin操作则需要遍历链表实现为O(n)
    [2] 让一个链表始终保持排序状态，这样Insert操作变得复杂需要遍历链表才能确定插入位置，为O(n)；deleteMin操作变为O(1)
    堆也恰恰提供了这样的操作实现。并综合降低了Insert，deleteMin操作的复杂度。

    我们常指的堆实际上是二叉堆，还有很多其他堆，如左式堆，斜堆，等等这里不介绍。！！
    binary heap, 是一棵完全二叉树（不一定是满二叉树）每个结点的父节点都小于等于该节点，根节点除外。

    完全二叉树有个非常非常重要的性质：可以用数组表示，而不需要用链表。一定要理解此性质！！！
    也就是说堆可以用数组实现。这样最大的好处是，可以在常数时间找到min，Insert操作为O(logn)，deleteMin操作平均为O(logn)

    对于堆排序的实现，为了思路清晰，方便，使用大顶堆。上面介绍的都是以小顶堆为基础的基本概念，将deleteMin改为deleteMax即可。
    排序的简单思路是，因为每次都能得到最大值（根结点），所以每做一次deleteMax操作即可去除一个最大值。这样做n次变得到排序结果。
    于是容易得到基本代码：
     void HeapSort(int p[], int size)
     {
        BuildMaxHeap(p, size);
        for(int i=size-1; i>0; i--)
        {
            DeleteMax(p, i);
        }
     }
    问题转化为如何实现BuildMaxHeap， DeleteMax操作。并有良好的时间，空间复杂度。
    设待排序列为数组p[n] 如果将p建成堆后，很明显p[0]为根结点，即最大值。
    考虑每次DeleteMax操作后，堆的大小变为n-1，可将p[0]与最后一个元素交换，于是DeleteMax操作的效果可视为：
    n个元素的堆序列 -> n-1个元素的堆序列|Max 如此循环下去便能完成排序。
    这里的BuildMaxHeap, DeleteMax均会用到下滤算法：如果某个元素影响堆序性质（父节点>=孩子）则将较大的孩子结点与其对换，如此往复下去，直至该元素到达正确位置。
    BuildMaxHeap，建堆的实现方式：由于所有树叶无需进行下滤（没有孩子），所以只对0 - size/2的结点进行下滤即可。
    DeleteMax 操作需要将最大值即p[0]与堆数组的最后一个元素（如p[n]）互换，然后对p[0]进行下滤操作即可得到一个 n-1个元素堆序列|max

    代码实现：
#include <iostream>
using namespace std;

//template <typename Comparable>

void BuildMaxHeap(int p[], int size);
void DeleteMax(int p[], int size);
void PercolateDown(int array[],int hole, int size);

void HeapSort(int p[], int size)
{
    BuildMaxHeap(p, size);
    for (int i=size; i>=1; i--)
    {
        DeleteMax(p, i);
    }
}

void BuildMaxHeap(int p[], int size)
{
    //由于所有树叶无需进行下滤（没有孩子），所以只对0 - size/2的结点进行下滤即可。
    for (int i=size/2-1; i>=0; i--)
        PercolateDown(p, i, size);
}

void DeleteMax(int p[], int size)
{
    int tmp;
    tmp = p[0];
    p[0] = p[size-1];
    p[size-1] = tmp;
    PercolateDown(p, 0, --size);
}

void PercolateDown(int array[],int hole, int size)
{
    int tmp = array[hole];
    int child=0;
    for (; (hole*2+1)<=(size-1); hole=child)
    {
        child = hole*2 + 1;
        if (child<size-1 && (array[child+1] > array[child]))
            child++;
        if (array[child]>tmp)
            array[hole] = array[child];
        else
            break;
    }
    array[hole] = tmp;
}

void PrintArray(int data[], int size)
{
    for (int i=0; i<size; ++i)
    {
        cout <<data[i]<<" ";
    }
    cout<<endl;
}

int main(int argc, const char** argv)
{
    int data[] = {20,34,4,53,43,42,6,67,193};
    int size = sizeof(data)/sizeof(data[0]);
    HeapSort(data, size);
    PrintArray(data, size);
    return 0;
}

补充：综合编程 , 其他综合 ,