堆的創建&堆排序&堆的應用

1. 堆的創建
   

堆其實是一種完全二叉樹，堆分為大堆和小堆，當滿足Key[i]>Key[2i+1]以及Key[i]>Key[2i+2]時是大堆，當滿足Key[i]<Key[2i+1]以及Key[i]<Key[2i+2]時是小堆。

#pragma once
#include<vector>
#include<iostream>
#include<assert.h>
using namespace std;
template<class T>
class Heap
{
public:
    Heap()
        :_a(NULL)
    {}

    Heap(const T* a,size_t size)
    {
        assert(a);
        for(size_t i=0;i<size;i++)
        {
            _a.push_back(a[i]);
        }
        for(int i=(_a.size()-2)/2;i>0;--i)
        {
            _AdjustDown(i);
        }
    }
    void Push(const T& x)
    {
        _a.push_back(x);
        _AjustUp(_a.size()-1);
    }
    void Pop()
    {
        assert(_a.empty());
        swap(_a[0],_a[a.size()-1]);
        _AdjustDown();
    }
protected:
    void _AdjustDown(size_t parent)
    {
        size_t child = parent*2+1;
        while(child > 0)
        {
            if(_a[child] < _a[child+1] && child<_a.size())
            {
                ++child;//如果左孩子比有孩子大的話，不做處理，反之，使得大的變成child = child+1;
            }
            if(_a[child]>_a[parent])   //每次交再向下調整
            {
                swap(_a[child],_a[parent]);
                parent = child;
                child = parent*2+1;
            }
            else 
            {
                break;
            }
        }
    }
    void _AjustUp(size_t child)
    {    
        int parent =  (child-1)/2;
        while(child > 0)  //這里必須判斷孩子下標，否則很危險。如果要用父親的判斷，則應該把size_t改為int
        {
            if(_a[parent]<_a[child])
            {
                swap(_a[parent],_a[child]);
                child = parent;
                parent = (child-1)/2;
            }
            else
            {
                break;
            }
        } 
    }
protected:
    vector<T> _a;
};
void TestHeap()
{
    int a[] = {10,11,13,12,16,18,15,17,14,19};
    Heap<int> Hp1(a,sizeof(a)/sizeof(a[0]));
    Hp1.Push(20);
}
int main()
{
     TestHeap();
    system( "pause");
    return 0;
}

2.堆排序思想

利用大根堆小根堆堆頂元素是最大記錄（最小記錄），使得每次從無序中選擇最大（最小記錄）就變得簡單了。這里采用大根堆思想，

1)將初始待排序關鍵字序列(R1,R2....Rn)構建成大頂堆，此堆為初始的無序區；

2)將堆頂元素R[1]與最后一個元素R[n]交換，此時得到新的無序區(R1,R2,......Rn-1)和新的有序區(Rn),且滿足R[1,2...n-1]<=R[n]; 

3)由于交換后新的堆頂R[1]可能違反堆的性質，因此需要對當前無序區(R1,R2,......Rn-1)調整為新堆，然后再次將R[1]與無序區最 后一個元素交換，得到新的無序區(R1,R2....Rn-2)和新的有序區(Rn-1,Rn)。不斷重復此過程直到有序區的元素個數為n-1，則整個排 序過程完成。

//堆排序
#include<iostream>
#include<assert.h>
using namespace std;
void AjustDown(int a[],size_t n,int parent)
{
    assert(a);
    int child = parent*2+1;
    while(child<n)
    {
        if(child<n &&(a[child]<a[child+1]))
        {
            ++child;
        }
        if(a[child]>a[parent])
        {
            swap(a[child],a[parent]);
            parent = child;
        }
        else
        {
            break;
        }
    }
}
void HeapSort(int a[],size_t n)
{
    assert(a);
    for(int i=(n-2)/2;i>0;--i)
    {
        AjustDown(a,n,i);
    }
    for(int i = 0; i < n; ++i)
    {
        swap(a[0],a[n-i-1]);
        AjustDown(a,n-i-1,0);
    }
}
void Test()
{
    int a[]={2,1,4,3,5,6,0,4,7,8,9};
    HeapSort(a,sizeof(a)/sizeof(a[0]));
}
int main()
{
    Test();
    system("pause");
    return 0;
}

算法分析：

從上述過程可知，堆排序其實也是一種選擇排序，是一種樹形選擇排序。只不過直接選擇排序中，為了從R[1...n]中選擇最大記錄，需比較n-1次，然后 從R[1...n-2]中選擇最大記錄需比較n-2次。事實上這n-2次比較中有很多已經在前面的n-1次比較中已經做過，而樹形選擇排序恰好利用樹形的 特點保存了部分前面的比較結果，因此可以減少比較次數。對于n個關鍵字序列，最壞情況下每個節點需比較log2(n)次，因此其最壞情況下時間復雜度為 nlogn。堆排序為不穩定排序，不適合記錄較少的排序。

3.堆的應用

例：100W個數中找出最大的100個

1  小根堆；
2  堆固定大小為100；
3  堆元素個數小于100時直接加入堆；
4  堆元素個數等于100時，與堆頂元素比較，比堆頂元素大的進堆，并調整堆；
5  遍歷結束時，堆中元素為100個最大數。

#pragma once
#include<iostream>
#include<assert.h>
#include<time.h>
#include<stdlib.h>
using namespace std;
const int N = 10000;
const int K = 100;
void _AjustDown(int TopK[],int size,int parent)
{
    assert(TopK);
    int child = parent*2+1;
    while( child < size)
    {
        if(child < size && (TopK[child] < TopK[child+1]))
        {
            ++child;
        }
        if(TopK[child] > TopK[parent])
        {
            swap(TopK[child],TopK[parent]);
            parent = child;
        }
        else
        {
            break;
        }
    }
}
void GetTop(int a[])
{
    assert(K < N);
    int TopK[K];
    for(int i=0;i<K;++i)
    {
        TopK[i] = a[i];
    }
    //建堆
    for(int i = (K-2)/2;i>= 0;--i)
    {
        _AjustDown(TopK,K,0);
    }
    for(int i=0;i<K;++i)
    {
        cout<<TopK[i]<<" ";
    }
}

void TestTopK()
{
    srand(time(0));
    int a[N];
    int TopK[K];
    
    for(int i= 0;i<N;++i)
    {
        a[i] = rand()%10000;
    }
    for(int i = N-K;i<N;++i)
    {
        a[i] = 10000+i;
    }
    GetTop(a);
}
int main()
{
    TestTopK();
    system("pause");
    return 0;
}