排序-堆排序

继续补数据结构。。。这次记录一下堆排序算法，具体的分析就不班门弄斧了，这两篇文章已经解释的很清楚了（自己脑子慢半天才明白。。）

• http://blog.csdn.net/jofranks/article/details/7802436
• http://blog.csdn.net/morewindows/article/details/6709644

直接上代码吧

#include <iostream>

using namespace std;

/**堆排序**/
void heapIfy(int* num, int dad, int size)
{
    int larger = 2*dad + 1;    //暂时将较大值指向左孩子
    while(larger < size)
    {
        if(larger+1 < size && num[larger+1] < num[larger]) //找左右孩子中较小的
            larger++;   //如果右孩子小，就指向右孩子(right = letf+1)

        if(num[larger] >= num[dad])   //比较父节点与较小子节点
            break;

        swap(num[dad], num[larger]);   //如果子节点小，与父节点交换
        dad = larger; //继续向下比较、交换，直到叶子节点（符合堆的条件）
        larger = 2*dad + 1;
    }
}

void _heapIfy(int* num, int dad, int size)   //递归写法
{
    int larger = 2*dad + 1;
    if(larger >= size)
        return;

    if(larger+1 < size && num[larger+1] < num[larger])
        larger++;

    if(num[larger] >= num[dad])
        return;

    swap(num[dad], num[larger]);
    _heapIfy(num, larger, size);
}

void buildHeap(int* num, int size)
{
    /*Tips:
        叶子结点已经是合格的堆，直接从叶子的父节点开始整理
        叶子 * 2 = 总结点
        建堆（大或小）取决于整理方法
    */
    for(int i = (size/2 - 1); i >= 0; i--)
        minHeapFixDown(num, i, size);
}

void heapSort(int* num, int n)
{
    /*
        将根结点与最末尾结点交换，删掉最后结点，再整理
        最后会整理成一个相反的堆
    */
    for(int i = n - 1; i >= 1; i--)
    {
        swap(num[i], num[0]);
        heapIfy(num, 0, i);
    }
}

int main()
{
    int num[10] = {9, 12, 17, 30, 50, 20, 60, 65, 4};
    buildHeap(num, 10);
    heapSort(num, 10);
    for(int i = 0; i < 10; i++)
        cout << num[i] << " ";
    return 0;
}

其他

堆这个数据结构在STL中也实现了，需要algorithm这个头文件，速度与我们自己编写相差无几，在STL系列之四 heap 堆这篇文章中有详细说明和测试（ps：还是我大快排厉害~~）
　　下次写写归并排序，To be continued~