c++로 작성한 최대 힙

자료구조 프로그래밍 과목을 배우면서 c++로 작성한 최대힙입니다.

maxheap.h

#include <iostream>

using namespace std;

 

template <class T>

class Maxheap

{

private:

        T *heap; //힙 배열

        int heapSize; //힙에 있는 요소 수

        int capacity; //힙의 크기

        void ChangeSize1D(T *&a, const int oldSize, const int newSize)

        {

               if(newSize<0)

                       throw "새로운 길이는 0보다 커야합니다.";

               T *temp=new T[newSize];

               int number=oldSize>newSize?newSize:oldSize; //min(oldSize, newSize)

               copy(a, a+number, temp);

               delete []a;

               a=temp;

        }

public:

        Maxheap(int theCapacity=10)

        {

               if(theCapacity<1)

                       throw "크기는 최소 1 이상이여야 한다.";

               capacity=theCapacity;

               heapSize=0;

               heap=new T[capacity+1];

        }

        void Push(const T &e)

        {

               if(heapSize==capacity) //요소의 수와 힙의 크기가 일치한다면

               {

                       //힙의 크기를 두배로 늘려준다

                       ChangeSize1D(heap, capacity, 2*capacity);

                       capacity*=2;

               }

               int currentNode=++heapSize;

               //루트가 아니고 부모의 요소가 삽입된 노드보다 크지 않을 때까지

               while(currentNode!=1&&heap[currentNode/2]<e)

               {

                       heap[currentNode]=heap[currentNode/2]; //부모를 자식의 위치로 내리고

                       currentNode/=2; //삽입할 위치를 인덱스만 이동

               }

               heap[currentNode]=e; //해당 위치에 값을 삽입

        }

        void Pop()

        {

               if(IsEmpty())

                       throw "힙은 비어있으므로 삭제할 수 없다.";

               heap[1].~T(); //루트 삭제

               T lastE=heap[heapSize--]; //마지막 index에 있는 노드 copy

               int currentNode=1;

               int child=2;

               while(child<=heapSize) //자식의 위치가 배열의 크기보다 작을때까지

               {

                       //왼쪽 자식보다 오른쪽 자식이 크면

                       if(child<heapSize&&heap[child]<heap[child+1])

                              child++;

                       if(lastE>=heap[child]) //lastE가 자식 노드보다 크면

                              break;

                       heap[currentNode]=heap[child]; //자식을 부모로 올림

                       currentNode=child; //부모의 인덱스를 자식의 인덱스로 낮춤

                       child*=2; //부모가 자식의 인덱스이므로 자식의 인덱스도 변경

               }

               heap[currentNode]=lastE; //해당 위치에 삽입

        }

        bool IsEmpty()

        {

               return heapSize==0;

        }

        T Top()

        {

               return heap[1];

        }             

        template <class T2>

        friend ostream &operator<<(ostream &, Maxheap<T2> &);

};

 

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;

        return os;

}

 

hw11.cpp

#include "maxheap.h"

 

int main(void)

{

        Maxheap<int> H;

        H.Push(15);

        H.Push(14);

        H.Push(21);

        H.Push(2);

        H.Push(10);

        H.Push(20);

       

        cout<<H;

       

        while(!H.IsEmpty())

        {

               cout<<H.Top()<<" ";

               H.Pop();

        }

        cout<<endl;

        return 0;

}

 

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~