通用堆排序.txt

C精彩编程百例源码

#include "stdafx.h"
#include <iostream>
using namespace std;

template<typename Type>
class MinHeap{
    private:
        Type *Arr;
        int CurrentSize;
        int MaxSize;
        void FilterDown(int start);
        void FilterUp(int start);
    public:
        MinHeap(int maxsize);
        MinHeap(Type a[], int n);
        ~MinHeap(){ delete [] Arr; }

        bool insert(Type const&);
        bool DeleteTop();
        Type GetTop() const { return Arr[0]; }
        bool empty() const { return CurrentSize==0; }
        bool full() const { return CurrentSize==MaxSize; }
        int size() const { return CurrentSize; }
        void clear() { CurrentSize=0; }
};

template<typename Type>
MinHeap<Type>::MinHeap(int maxsize)
{
    if(maxsize<=0){
        cerr<<"Heap size could not smaller than 1"<<endl;
        exit(1);
    }
    MaxSize=maxsize;
    Arr=new Type[MaxSize];
    CurrentSize=0;
}

template<typename Type>
MinHeap<Type>::MinHeap(Type a[], int n)
{
    if(n<=0){
        cerr<<"Heap size could not smaller than 1"<<endl;
        exit(1);
    }
    CurrentSize=MaxSize=n;
    Arr=new Type[MaxSize];
    for(int i=0; i<MaxSize; i++)
        Arr[i]=a[i];

    for(i=(CurrentSize-2)/2; i>=0; i--)
        FilterDown(i);
}

template<typename Type>
void MinHeap<Type>::FilterDown(int start)
{
    int i=start;
    int j=2*i+1;
    Type temp=Arr[i];
    while(j<CurrentSize){
        if(j<CurrentSize-1 && Arr[j]>Arr[j+1]) ++j;
        if(temp<=Arr[j])break;
        else{
            Arr[i]=Arr[j];
            i=j;
            j=2*j+1;
        }
    }
    Arr[i]=temp;
}

template<typename Type>
void MinHeap<Type>::FilterUp(int start)
{
    int j=start;
    int i=(j-1)/2;
    Type temp=Arr[j];
    while(j>0){
        if(Arr[i]<=temp)break;
        else{
            Arr[j]=Arr[i];
            j=i;
            i=(j-1)/2;
        }
    }
    Arr[j]=temp;
}

template<typename Type>
bool MinHeap<Type>::insert(Type const& d)
{
    if(full()==true){
        //cout<<"Heap is full"<<endl;

        return false;
    }
    Arr[CurrentSize]=d;
    FilterUp(CurrentSize);
    ++CurrentSize;
    return true;
}

template<typename Type>
bool MinHeap<Type>::DeleteTop()
{
    if(empty()==true){
        //cout<<"Heap is empty"<<endl;

        return false;
    }
    Arr[0]=Arr[--CurrentSize];
    FilterDown(0);
    return true;
}