Heap

Heap

힙은 힙 속성을 만족하는 완전 이진 트리(이진 힙의 경우)이다. 우선 순위가 가장 높은 원소를 빠르게 찾는 용도로 사용된다.

 

힙을 사용하면, 원소를 추가하는 연산, 가장 우선순위가 높은 연산을 O(logN)으로 수행할 수 있다. 우선순위가 가장 높은 수가 가장 큰수라면 최대힙, 가장 작은 수라면 최소힙이라 부른다.

 

힙 속성 : 부모 노드는, 항상 자식 노드보다 우선순위가 높다.

따라서 힙은 힙 속성, 완전 이진 트리를 만족해야한다.

BBST를 쓰면 안되나?

BBST보다 힙이 훨씬 빠르다. BBST도 같은 시간 복잡도를 가지며, 심지어 우선 순위가 가장 낮은 원소도 가져올 수 있지만, 같은 시간 복잡도라도 힙은 간단한 작업을 수행하기에 더 빠르다. BBST는 트리의 균형을 맞추기 위해 복잡한 작업을 수행하여 더 느리다. 때문에 같은 일을 한다면 힙 대신 BBST를 쓰는 것은 좋지 않다.

구현

힙은 완전 이진 트리이기 때문에 배열로 쉽게 구현할 수 있다.

배열의 0번 인덱스를 루트 노드라 했을 때, i번 노드의 왼쪽 자식은 2 * i + 1, 오른쪽 자식은 2 * i + 2번이며 i번 노드의 부모는 (i-1) / 2번 노드이다. N개의 노드가 있다면 N크기의 배열로 힙을 구현할 수 있다.

 

원소 삽입

힙은 힙 속성과 완전 이진 트리 규칙을 만족해야한다. 루트 노드부터 시작해 리프 노드까지 교환해 내려간다면 힙 속성은 만족하지만 완전 이진 트리 규칙을 만족시키는 것이 까다롭다. 이때 완전 이진 트리 규칙부터 만족시키면 쉽게 구현할 수 있다.

1. 마지막 리프 노드에 원소를 넣는다(= 완전 이진 트리 규칙 만족)

2. 1번의 리프 노드부터 시작해 루트 노드까지 교환한다.(= 힙 속성 만족)

 

최대 원소 꺼내기

루트를 삭제한다. 그리고 원소 삽입과 같이 완전 이진 트리 규칙을 먼저 고려하는 것이 쉽다.

1. 마지막 리프 노드를 루트 노드에 덮어 씌운다.(= 완전 이진 트리 규칙 만족)

2. 루트 노드부터 시작해 리프 노드까지 교환한다. 이때 자식 노드 중 우선 순위가 높은 노드와 교환한다.(= 힙 속성 만족)

class PQ {
    static final int MAX_SIZE = 10000000;
    int[] arr;
    int size;

    PQ() {
        arr = new int[MAX_SIZE];
        size = 0;
    }

    void offer(int node) {
        arr[size] = node;
        size++;

        int cur = size-1;
        while(cur > 0) {
            int parent = (cur-1) / 2;
            if(arr[parent] >= arr[cur]) break;
            swap(cur, parent);
            cur = parent;
        }
    }

    int poll() {
        int top = arr[0];
        arr[0] = arr[size-1];
        size--;

        int cur = 0;
        int leftChild = cur * 2 + 1;
        int rightChild = cur * 2 + 2;
        while(leftChild < size) {
            int child = leftChild;
            if(rightChild < size && arr[rightChild] > arr[child]) child = rightChild;

            if(arr[cur] >= arr[child]) break;

            swap(cur, child);
            cur = child;
            leftChild = cur * 2 + 1;
            rightChild = cur * 2 + 2;
        }
        return top;
    }

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

    void swap(int idx1, int idx2) {
        int temp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = temp;
    }
}