max-heap, min-heap - 이진트리의 활용

heap - 이진트리의 활용

실제로 상당히 유용하게 쓰이는 heap에 대해서 알아보도록 하자.

heap이란 이진트리를 활용한 상당히 재밌는 구조이다. 

주로 max-heap, min-heap으로 가장 큰값 또는 가장 작은 값을 빠르게 찾기 위해서 사용이된다.

min, max 뿐만 아니라 원하는 조건대로 compare을 하면 가장 원하는 값을 빠른시간에 뽑아낼 수 있다.

아직 설명하기 전이지만 , sort를 한 후에 골라내는게 더 빠르지 않냐 라는 생각을 할 수 도있다.

이 heap의 장점이라면, 삽입, 삭제를 했을 때 추가적인 sort가 필요없다는 것이다.

이 정도로 서론을 끝내고 직접 적으로 heap에 대해서 알아보자.

1. heap?

heap이란 최대값 또는 최소값을 빠르게 찾기위해서 고안된 트리모양의 자료구조이다. 

말 그대로 max-heap은 가장 큰값을 빠르게 찾기 위한 것이고, min-heap은 가장 작은 값을 빠르게 찾기 위한 것이다.

이 heap을 구현하는 데에도 Binary heap, Binomial heap, Fibonacci heap이(내가 아는 한도에서) 존재한다.

하지만 이번 글은 가장  내 수준에서 많이 쓰는 이진 힙(Binary heap)을 기준으로 설명하겠다.

이진 힙(Binary heap)은 기본적으로 완전이진트리 이여야 한다.

이진 힙(Binary heap)은 min-heap, max-heap으로 구별을 할 수 있을 것 같다.

min-heap : 부모노드의 값이 자식노드의 값보다 작다.

max-heap : 부모노드의 값이 자식노드의 값보다 크다.

이 2가지 조건만 만족하면서 트리를 만들게 되면 쉽게 heap을 구성할 수 있을 것이다.

간단하게 max-heap의 예를 하나 들어보겠다.

위의 트리를 보면 

조건 1 : 완전이진 트리 => 만족한다.

조건 2 : 부모노드의 값이 자식노드의 값보다 크다

=> 8은 4와 6보다 크다.

=> 4는 2와 3보다 크다.

=> 만족한다.

따라서 위의 트리는 max-heap이라고 할 수가 있다.

이렇게 끝내기에는 너무 허무하고 뭐지라는 생각이 들수가 있다.

이 heap은 삽입과 삭제를 하는 과정에서 이진트리의 특성을 잘 살리기 때문에 삽입과 삭제에 대해서 알아보아야 한다.

1.1 삽입

삽입의 과정은 간단한 순서를 따라가면 된다.

1. 완전이진트리의 가장 마지막 원소에 원하는 값을 삽입한다.

2. 부모가 나보다 작다면(Max_Heap기준) 부모와 자식의 값을 교환한다.

3. 2번에서 부모가 없거나, 부모가 자식보다 클 경우에 끝

밑에 그림으로 10이 삽입되어지는 과정을 간단하게 살펴보자.

동작 과정을 보면 알겠지만 내가 삽입을 한다고 했을 때 최대 이 트리의 높이만큼 비교를 해야한다.

트리의 높이는 트리의 노드의 수가 N이라고 할때 완전이진트리 이기 때문에 Log(N)이다.(높이 h일때 원소는 1+2+4+...+2^h-1)

따라서 삽입하는 과정에서의 복잡도는 O(logN) 이라고 볼수 있다.

자세한 증명은 생략하겠다.

1.2 삭제

삭제하는 과정도 삽입하는 과정처럼 그리 복잡하지는 않다.

삭제라고는 하지만 실제로는 Max_heap 기준으로 가장 큰값을 뽑아 낼 때의 작업을 의미하는 것이다.

당연히 반대로 Min_heap의 경우는 가장 작은 값을 뽑아내는 경우를 의미하는 것이다.

1. root(원하는값)노드를 heap의 가장 마지막 노드와 교환한다.

2. 교환된 가장 마지막 노드를 삭제한다.

3. 새로운 root노드의 알맞는 위치를 찾아서 내려간다.

그림을 통해 최대값을 삭제(뽑아내는) 과정을 살펴 보도록 하자.

그림에는 마지막에 한번만 교환을 하게 되지만 자식보다 값이 작지 않을 때까지 계속 교환을 해 주어야 한다.

깊게 여겨볼 과정은자신과 자식 2명과 비교를 하였는데 둘다 나보다 큰 경우이다.

이 경우에 2가지 경우가 발생을 하게 되는데

1. 나보다 큰 2명의 자식중 작은 값을 가지는 노드를 선택한다.

2. 나보다 큰 2명의 자식 중 큰 값을 가지는 노드를 선택한다.

하나씩 생각 해보자.

1. 위의 그림의 경우에서 4와 8중 4를 선택한 경우이다.

   6과 4를 교환했다고 하자. 4가 root가 되고 이것은 8보다 작은 값이다.

   즉 교환된 4는 다시 8과 비교를 당해 또 다시 제자리를 찾아가야 한다.

2. 위의 그림의 경우에서 4와 8중 큰값인 8을 선택했다고 하자.

   6과 8을 교환 한 경우 8은 4와 6 두 값보다 크기 때문에 아무런 문제가 발생하지 않는다.

따라서 우리는 2개의 교환할 수 있는 경우가 발생 하였을 경우에는 더 큰값을 가지는 노드를 선택하는 것이 옳다.

이 과정 또한 입력과 마찬가지로, 삭제를 한 후에 자신의 자식들을 비교하면서 자리를 찾아가는 것이기 때문에

시간복잡도는 O(logN)이라는 것을 알 수 있다.

2. heap의 구현

Binary heap의 구현은 그렇게 간단하지는 않다. 하지만 구현할줄 모르는 것은 모르는 것이기 떄문에 구현해보도록 하겠다.

다른 자료구조와 동일하게 C++ class로 구현을 해 보겠다.

직관적으로 구현을 한거라 소스가 이쁘게 나오지는 않았다 단순히 참고,공부용으로만 이용하길 바란다.

#include <iostream>
using namespace std;
 
//Max_heap
class Heap {
private:
    int* heap;
    int capacity;
    int currentSize;
 
 
    void swap(int* a, int *b) {
        int t = *a;
        *a = *b;
        *b = t;
    }
 
 
public :
 
    //힙 생성자
    Heap(int Capacity)  : capacity(Capacity){
        heap = new int[Capacity];
        currentSize = 0;
    }
    //힙 파괴자
    ~Heap() {
        delete[] heap;
    }
 
 
    //삽입
    void Insert(int val) {
        //Heap Size Check
        if (currentSize >= capacity) {
            printf("Heap is full!");
            return;
        }
        //마지막에 원소 삽입
        int mPos = currentSize++;
        heap[mPos] = val;
        //부모값보다 내가 크다면 교환 교환 교환
        int parPos = (mPos - 1) / 2;
        while (heap[mPos]>heap[parPos]) {
            swap(&heap[mPos], &heap[parPos]);
            mPos = parPos;
            parPos = (mPos - 1) / 2;
        }
    }
    //삭제, 추출
    int pop() {
        if (currentSize <= 0) {
            printf("Heap is Empty!!!\n");
            return NULL;
        }
        int returnVal = heap[0];
        //1. root와 가장 마지막 노드 교환
        swap(&heap[0],&heap[currentSize-1]);
        //2. 교환된 마지막 노드 삭제
        heap[currentSize - 1] = NULL;
        currentSize--;
        //3. 새로운 root노드 자리 찾아가기.
        int root = 0;
        int leftChild;
        int rightChild;
 
        while (root<=currentSize-1) {
            leftChild = (root + 1) * 2 - 1;
            rightChild = (root + 1) * 2;
 
            if (leftChild >= currentSize) {
                //Child 존재 X
                break;
            }
            else if (rightChild >=currentSize) {
                //왼쪽 Child만 존재
                if (heap[leftChild] > heap[root]) {
                    swap(&heap[leftChild], &heap[root]);
                    root = leftChild;
                }
                else break;
            }
            else {
                //양쪽 Child 존재
                if (heap[leftChild] > heap[root] && heap[rightChild] > heap[root]) {
                    if (heap[leftChild]<heap[rightChild]) {
                        swap(&heap[rightChild], &heap[root]);
                        root = rightChild;
                    }
                    else {
                        swap(&heap[leftChild], &heap[root]);
                        root = leftChild;
                    }
                }
                else if (heap[leftChild] > heap[root]) {
                    swap(&heap[leftChild], &heap[root]);
                    root = leftChild;
                }
                else if (heap[rightChild] > heap[root]) {
                    swap(&heap[rightChild], &heap[root]);
                    root = rightChild;
                }
                else {
                    break;
                }
            }
 
        }
        return returnVal;
        
    }
    int GetTop() {
        if(currentSize>=1)    return heap[0];
        else return -1;
    }
 
};
 
 
int main() {
 
    Heap heap = Heap(100);
    for (int i = 1; i <= 8; i++) heap.Insert(i);
    for (int i = 1; i <= 8; i++) heap.Insert(8-i+1);
    for (int i = 1; i <= 16; i++) printf("%d ", heap.pop());
 
 
    return 0;
}

깃허브 링크