#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;        };  

堆可以被看作是一个完全二叉树，小堆排序利用小根堆堆顶记录的关键字最小这一个特征，使得从当前无序区中选取最小关键字并进一步记录操作变的简单。