최대 힙 구현

 

코드

#include <iostream>

using namespace std;

template<typename T>
class HEAP {
    int size;
    T *heapArr;
private:
    void pushSwap(int n){
        if( n ==1) return; //최상위 노드
        int parent = n /2 ;
        if(heapArr[parent] <heapArr[n]){ //부모노드보다 자식노드가 크면
            T tmp =heapArr[parent];
            heapArr[parent] = heapArr[n];
            heapArr[n] = tmp;

            pushSwap(parent);
        }
    }
    void popSwap(int n){
        int leftChild = (n * 2 <= size ? n * 2 : -1);
        int rightChild = (n * 2 + 1 <= size ? n * 2 + 1 : -1);
        int child; 
        //자식이 둘 다 없을 때
        if(leftChild == -1 && rightChild == -1 ) child = -1;
        //왼쪽 자식만 있을 때 (오른쪽만 있는 경우는 당연히 없다)
        else if (leftChild != -1 && rightChild == -1 ) child = leftChild ;
        //자식이 둘 다 있을 때
        else child = (heapArr[leftChild]> heapArr[rightChild] ? leftChild : rightChild) ;

        if(child == -1) return;
        if(heapArr[child] > heapArr[n]){ //자식이 더 크다면
            T tmp =heapArr[child];
            heapArr[child] = heapArr[n];
            heapArr[n] = tmp;

            popSwap(child);
        }
    }
public:
    HEAP(int n){
        size=0;
        heapArr =new int[n+1];
    }
    ~HEAP(){
        delete[] heapArr;
    }
    bool empty(){
        if(size == 0 ) return true;
        return false;
    }
    int amount(){
        return size;
    }
    T top(){
        return  empty() ? -1 : heapArr[1];
    }
    void push(int value){
        heapArr[++size]=value;
        pushSwap(size);
    }
    void pop(){
        if (empty())  // size ==0 이면 pop할 것이 없으니 return 
            return;
 
        heapArr[1] = heapArr[size--];
        popSwap(1);
    }
    void show(){
        for(int i =1 ; i< size+1 ; i++){
            cout<<heapArr[i]<<", ";
        }
        cout<<endl;
    }
};

최댓값을 구하기 위해 최악의 경우가 생겨도 힙은 완전 이진 트리이므로 항상 O(lgN)의 시간에 해결

주의점 : 최대힙은 요소의 삽입, 삭제 속에서 최댓값을 빠르게 찾아가는 과정이지, 내림차순으로 정렬 된 것이 아님을 알아야 한다.

 

 

최소 힙

int mian()
{
    HEAP<int> maxh(size);
    HEAP<int> minh(size);
    for (int i = 0; i < size; i++)
    {
        maxh.push(i);
        minh.push(i * -1);
    }
    maxh.show();
    minh.show();
}

결과 : maxh.show() :  9,  8,  5,  6,  7,  1,  4,  0,  3,  2,

          minh.show() : 0, -1, -2, -3, -4, -5, -6, -7, -8, -9,

최소 힙을 알기 위해서 -1를 곱해 주면 된다. minh.show() 결과에서 다시 -1를 곱해주면 

0, 1, 2, 3, 4, 5, 6, 7, 8, 9 가 되고 맨 앞에 있는 것이 최고 루트이므로 0이 최솟값이라는 것을 알 수 있다.

 

 

 

 

 

출처: https://www.crocus.co.kr/1184 [Crocus]