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

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

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点！
本站所提供的图片等素材，版权归原作者所有，如需使用，请与原作者联系。