C++排序（小堆排序）

    #include<iostream>


#include<string>  
using namespace std;  

template<class Type>  
class MinHeap  
{  
public:  
    MinHeap(int sz=DefaultSize)  
    {  
        capacity = sz>DefaultSize?sz:DefaultSize;  
        heap = new Type[capacity];  
        size = 0;  
    }  
    MinHeap(Type ar[], int n)  
    {  
        capacity = n>DefaultSize?n:DefaultSize;  
        heap = new Type[capacity];  
        for(int i=0; i<n; ++i)  
        {  
            heap[i] = ar[i];  
        }  
        size = n;  

        int pos = n/2-1;  
        while(pos >= 0)  
        {  
            SiftDown(pos,n-1);  
            pos--;  
        }  
    }  
    ~MinHeap()  
    {  
        delete []heap;  
        heap = NULL;  
    }  
    void Show()const  
    {  
        for(int i=0; i<size; ++i)  
        {  
            cout<<heap[i]<<" ";  
        }  
        cout<<endl;  
    }  
    bool IsEmpty()const  
    {  
        return size == 0;  
    }  
    bool IsFull()const  
    {  
        return size >= capacity;  
    }  
    void MakeHeap()  
    {  
        size = 0;  
    }  
    Type ReMoveMin()  
    {  
        Type tmp = heap[0];  
        heap[0] = heap[size-1];  
        size--;  
        SiftDown(0,size-1);  
        return tmp;  
    }  
    void Sort()  
    {  
        Type *data = new Type[size];  
        int i = 0;  
        while(!IsEmpty())  
        {  
            data[i++] = ReMoveMin();  
        }  

        size = i;  
        for(i=0; i<size; ++i)  
        {  
            heap[i] = data[i];  
        }  
        delete []data;  
        data = NULL;  
    }  
    void Insert(const Type &x)  
    {  
        heap[size] = x;  
        SiftUp(size);  
        size++;  
    }  

private:  
    void SiftUp(int start)  
    {  
        int j = start;  
        int i = (j-1)/2;  

        Type tmp = heap[j];  

        while(j>0)  
        {  
            if(tmp > heap[i])  
                break;  
            else  
            {  
                heap[j] = heap[i];  
                j = i;  
                i = (j-1)/2;  
            }  
        }  
        heap[j] = tmp;  
    }  
    void SiftDown(int start, int end)  
    {  
        int i = start;  
        int j = 2*i+1;  

        Type temp = heap[i];  

        while(j <= end)  
        {  
            if(j<end && heap[j] > heap[j+1])  
                j = j+1;  
            if(temp < heap[j])  
                break;  
            else  
            {  
                heap[i] = heap[j];  
                i = j;  
                j = 2*i+1;  
            }  
        }  
        heap[i] = temp;  
    }  

private:  
    enum{DefaultSize = 10};  
    Type *heap;  
    int capacity;  
    int size;  
};  </pre> 


 堆可以被看作是一個完全二叉樹，小堆排序利用小根堆堆頂記錄的關鍵字最小這一個特征，使得從當前無序區中選取最小關鍵字并進一步記錄操作變的簡單。