힙(Heap) Max Heap, Min Heap

 

---

힙의 정의 

A Heap is a special Tree-based data structure in which the tree is a complete binary tree.

 

힙은 트리, 그 중 완전 이진 트리를 기반으로 한 자료구조이다.

힙이 되기 위해서는 완전 이진 트리이면서, 부모 노드가 가진 데이터 값은 자식 노드가 가진 데이터 값보다 무조건 크거나(이 경우 Max Heap), 혹은 작아야(이 경우 Min Heap) 한다.

 

출처: https://www.geeksforgeeks.org/heap-data-structure/

 

위 사진을 보면, Max Heap의 경우 모든 부모 노드는 자식 노드보다 데이터의 값이 크고 Min Heap의 경우 모든 부모 노드가 자식 노드보다 데이터의 값이 작은 것을 확인할 수 있다. 

따라서 루트 노드에 Min Heap의 경우 항상 트리의 최솟값이, Max Meap의 경우 항상 트리의 최댓값이 위치한다. 

이러한 성질으로, 힙은 우선순위를 자료구조 내에 유지하여, 최댓값 혹은 최솟값을 빠르게 찾아낼 수 있도록 고안된 자료구조이다.

우선 순위 큐를 구현할 때 사용하는 자료구조이기도 하다.

 

데이터 추가 과정

데이터가 추가될 경우, 어떻게 힙 내의 자료구조를 유지하는지 알아보자.

다음은 Max Heap의 데이터 추가 과정이다. 

1. 추가된 데이터는 완전 이진 트리의 법칙에 따라 마지막 위치에 들어간다.
2. 부모 노드와 자신과의 데이터 값을 비교하여 부모가 자신보다 큰 지를 확인(확실히)한다. 만약, 자신이 부모 노드의 값보다 크다면 부모 노드와 자리를 바꾼다. (=자신이 부모 노드가 된다.)
3. 이 과정을 자신보다 큰 부모 노드가 나타나거나, 혹은 루트 노드가 될 때까지 반복한다.

(Min Heap의 경우 부모 노드의 값이 자신보다 작은지를 확인(확실히)하며, 나머지는 Max Heap과 같다.)

 

예시

• 데이터 20,2,15,10의 추가

 

위 그림은 10이 추가된 당시이다. 이제 완전 이진 트리의 규칙대로 4번(빨간 숫자)에 10이 추가되고, 이제 부모 노드와 자신을 비교한다. 현재 부모 노드(2)가 자신(10)보다 작으므로 서로 위치를 바꾼다.

 

이제 다시 부모 노드와 자신의 값을 비교한다. 현재 부모 노드(20)가 자신(10)보다 크므로, 데이터 추가의 과정이 끝난다. 

 

• 데이터 30의 추가

 

위 그림은 30이 추가된 당시이다. 역시 마지막 5번에 추가되며, 부모 노드인 2번과 자신의 값을 비교한다. 현재 부모 노드(10)가 자신(30)보다 작으므로 서로 위치를 바꾼다.

 

이제 다시 부모 노드와 자신의 값을 비교한다. 현재 부모 노드(20)가 자신(30)보다 작으므로, 서로 위치를 바꾼다.

 

 

이제 자신이 루트 노드가 되어 비교할 부모 노드가 없으므로 데이터 추가 과정이 끝이 난다.

 

시간복잡도

힙에 데이터를 추가하는 경우 방문하는 노드의 최대 개수는 완전 이진 트리의 높이와 동일함을 알 수 있다.

아무리 위로 올라가도 루트 노드가 되면 데이터 추가 과정이 끝나기 때문이다.

높이가 k일 때, 이진 트리가 가질 수 있는 최대 노드의 수 n의 값은 n=\(2^k-1\) ,  \(2^k=1+n\)이다. 

이를 통해 k의 값을 \(k=log2{(n+1})\)로 유추할 수 있다.

따라서 힙의 노드의 개수가 N일 때, 데이터 추가시 시간복잡도는 \(O(log_{2}N)\) 이다. 

데이터 삭제 과정

데이터가 삭제될 경우, 어떻게 힙 내의 자료구조를 유지하는지 알아보자.

다음은 Max Heap의 데이터 삭제 과정이다. 

1. 삭제는 항상 루트 노드에서 발생한다. (가장 큰 우선순위를 가진 노드부터 삭제된다.)
2. 가장 맨 뒤의 노드를 루트 노드로 옮긴다.
3. 자신과 자식 노드와의 데이터 값을 비교하여 자신이 자식 노드보다 큰 지를 확인(확실히)한다. 만약, 자식 노드의 값이 자신보다 크다면 자식 노드와 자리를 바꾼다. (=자신이 자식 노드가 된다.)
4. 이 과정을 자신보다 큰 자식노드가 없을 때까지, 혹은 리프 노드가 될 때까지 반복한다.

(Min Heap의 경우 자신이 자식 노드보다 작은 지를 확인(확실히)하며, 나머지는 Max Heap과 같다.)

 

예시

 

위 그림의 Max Heap에서 데이터가 삭제 시 루트 노드인 30이 삭제되게 된다. 그에 따라 가장 마지막 노드인 5번 노드가 1번 루트 자리에 들어간다.

 

이제 루트 노드가 된 10은 자식 노드와 자신을 비교하여 자신이 자식 노드보다 큰 지를 확실히 해야 한다.

먼저 왼쪽 자식인 20과 자신을 비교한다. 자식 노드(20)이 자신(10)보다 크므로, 서로 위치를 바꾼다.

 

이제 자식 노드와 자신을 비교한다. 자식 노드(2)보다 자신(10)이 크므로, 데이터 삭제 과정이 끝이난다. 

 

시간복잡도

힙에 데이터를 삭제하는 경우 역시, 방문하는 노드의 최대 개수는 완전 이진 트리의 높이와 동일함을 알 수 있다.

아무리 아래로 내려가도 리프 노드가 되면 데이터 삭제 과정이 끝난다.

따라서 힙의 노드의 개수가 N일 때, 데이터 삭제시 시간복잡도는 \(O(log_{2}N)\) 이다. 

 

구현

Java로 정수의 Max Heap인 Priority Queue를 구현하였다.

public class PriorityQueue {
    int size;
    int[] queue;
    
    public PriorityQueue(int capacity) {
        this.queue = new int[capacity];
        size = 0;
    }

    public void add(int data) {
        if(isFull()) {
            throw new IllegalStateException("Priority Queue is Full.");
        }

        queue[size++] = data;
        int curIdx = size-1;

        while(curIdx>0) {
            int parentIdx = (curIdx-1)/2;
            // Max Heap
            if(queue[parentIdx] >= queue[curIdx]) {
                break;
            }

            swap(parentIdx, curIdx);
            curIdx = parentIdx;
        }
    }

    public Object remove() {
        if(isEmpty()) {
            throw new IllegalStateException("Priority Queue is Empty.");
        }
        int popData = queue[0];
        int replacedData = queue[--size];
        int curIdx = 0;
        queue[0] = replacedData;

        while(curIdx*2+1<size) { 
        	// 왼쪽 자식이 존재한다면
            int childIdx = curIdx*2+1;

            if (childIdx+1<size && queue[childIdx+1]>queue[childIdx]) { 
                // 오른쪽 자식이 존재하고, 만일 오른쪽 자식이 더 크다면
                childIdx = childIdx + 1;
            }

            if (queue[curIdx] >= queue[childIdx]) {
                break;
            }

            swap(curIdx, childIdx);
            curIdx = childIdx;
        }
        return popData;
    }

    private void swap(int i, int j) {
        int temp = queue[i];
        queue[i] = queue[j];
        queue[j] = temp;
    }

    public boolean isFull() {
        return size == queue.length;
    }

    public boolean isEmpty() {
        return size == 0;
    }
}