MaxHeap 구현

#include<iostream>
using namespace std;
 
 
template<class T>
void ChangeSizeID(T* &a,const int oldSize,const int NewSize);
 
template<class T>
class Maxheap{
public:
        Maxheap(int);
        void Push(const T& e);
        void Pop();
        bool IsEmpty(){return heapSize==0;}
        T Top(){ return heap[1];        }
private:
        int heapSize;
        int capacity;
        T *heap;
template<class T2>
friend ostream& operator<<(ostream&,Maxheap<T2>&);
};
 
template<class T>
void ChangeSizeID(T *&a,const int oldSize,const int newSize)
{
        T arr[oldSize+1];
        for(int i=1;i<=oldSize;i++){
                arr[i]=a[i];
        }
        delete []a;
        a=new T[newSize];
        for(int i=1;i<=oldSize;i++){
                 a[i]=arr[i];
        }
 
}
 
template<class T>
ostream& operator<<(ostream& os,Maxheap<T>& H){
        os<<"<Heap Contents> ";
        for(int i=1;i<=H.heapSize;i++)
                os<<i<<":"<<H.heap[i]<<" ";
        os<<endl;
}
 
template<class T>
Maxheap<T>::Maxheap(int theCapacity=10):heapSize(0){
        if(theCapacity<1) throw "Must be +ve";
        capacity=theCapacity;
        heap=new T[capacity+1];
}
 
template<class T>
void Maxheap<T>::Push(const T& e){
        if(heapSize==capacity){
                ChangeSizeID(heap,capacity+1,2*capacity+1);
                capacity*=2;
        }
        int currentNode=++heapSize;
        while(currentNode!=1&&heap[currentNode/2]<e)
        {
                heap[currentNode]=heap[currentNode/2];
                currentNode/=2;
        }
        heap[currentNode]=e;
}
 
template<class T>
void Maxheap<T>::Pop(){
                if(IsEmpty()) throw "Heap is empty.Cannot delete.";
                heap[1].~T();
                T lastE=heap[heapSize--];
                int currentNode=1;
                int child=2;
                while(child<=heapSize)
                {
                        if(child<heapSize &&heap[child] <heap[child+1]) child++;
 
                        if(lastE>=heap[child]) break;
 
                        heap[currentNode]=heap[child];
                        currentNode=child; child*=2;
                }
                heap[currentNode]=lastE;
}
 
 
 

maxheap.h 헤더파일 

#include<iostream>
#include<queue>
using namespace std;
int main()
{
        priority_queue<int> maxPQ;
        maxPQ.push(15); maxPQ.push(14);
        maxPQ.push(21); maxPQ.push(2);
        maxPQ.push(10); maxPQ.push(20);
 
        while(!maxPQ.empty())
        {
                cout<<maxPQ.top()<<" ";maxPQ.pop();
        }
        cout<<endl;
}
 
 
 
 

출력 결과

21 20 15 14 10 2