Heap 알아보기

Heap이란?

완전 이진 트리(Complete Binary Tree)를 기본으로 한 자료구조로, 부모 노드와 자식 노드 간에 특정한 순서가 존재하는 자료구조입니다. 최대 힙(Max Heap)은 부모 노드가 자식 노드보다 크거나 같고, 최소 힙(Min Heap)은 부모 노드가 자식 노드보다 작거나 같습니다.

특징

1. 완전 이진 트리 구조를 가짐 (마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있어야 함)
2. 배열로 구현 가능 (왼쪽 자식: 2i + 1, 오른쪽 자식: 2i + 2, 부모: (i-1)/2)
3. 우선순위 큐 구현에 주로 사용됨
4. 힙 정렬(Heap Sort)의 기반이 되는 자료구조

시간 복잡도에서의 Heap

데이터의 삽입, 삭제, 탐색을 기준으로 살펴보겠습니다.

1. 삽입 (add/offer)

Java의 PriorityQueue를 통해 구현된 Heap의 삽입 과정을 살펴보겠습니다.

public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException();
    modCount++;
    int i = size;
    if (i >= queue.length)
        grow(i + 1);
    siftUp(i, e);
    size = i + 1;
    return true;
}

private void siftUp(int k, E x) {
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = queue[parent];
        if (comparator.compare(x, (E) e) >= 0)
            break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = x;
}

삽입은 다음과 같은 과정으로 진행됩니다:

1. 새로운 요소를 트리의 마지막 위치에 추가
2. 부모 노드와 비교하여 힙의 특성을 만족할 때까지 위로 이동(siftUp)

최악의 경우, 새로 삽입된 노드가 루트까지 이동해야 할 수 있으므로 트리의 높이만큼 비교와 교환이 필요합니다. 완전 이진 트리의 높이는 log N이므로, 시간복잡도는 O(log N)입니다.

2. 삭제 (remove/poll)

힙에서의 삭제는 주로 루트 노드를 삭제하는 작업을 의미합니다.

public E poll() {
    final Object[] es;
    final E result;

    if ((result = (E) ((es = queue)[0])) != null) {
        modCount++;
        final int n;
        final E x = (E) es[(n = --size)];
        es[n] = null;
        if (n > 0) {
            final Comparator<? super E> cmp;
            if ((cmp = comparator) == null)
                siftDownComparable(0, x, es, n);
            else
                siftDownUsingComparator(0, x, es, n, cmp);
        }
    }
    return result;
}

private void siftDownComparable(int k, E x, Object[] es, int n) {
    // assert n > 0;
    Comparable<? super E> key = (Comparable<? super E>)x;
    int half = n >>> 1;           // loop while a non-leaf
    while (k < half) {
        int child = (k << 1) + 1; // assume left child is least
        Object c = es[child];
        int right = child + 1;
        if (right < n &&
            ((Comparable<? super E>) c).compareTo((E) es[right]) > 0)
            c = es[child = right];
        if (key.compareTo((E) c) <= 0)
            break;
        es[k] = c;
        k = child;
    }
    es[k] = key;
}

삭제 과정은 다음과 같습니다:

1. 루트 노드 제거
2. 마지막 노드를 루트로 이동
3. 새로운 루트를 자식 노드들과 비교하여 힙의 특성을 만족할 때까지 아래로 이동(siftDown)

마찬가지로 최악의 경우 루트에서 리프까지 이동해야 하므로 시간복잡도는 O(log N)입니다.

3. 탐색 (peek)

힙에서는 루트 노드의 값만 바로 확인할 수 있습니다.

public E peek() {
    return (E) queue[0];
}

루트 노드의 값을 바로 반환하므로 시간복잡도는 O(1)입니다.

특정 값을 찾는 탐색은 힙의 목적에 맞지 않으며, 필요한 경우 전체 노드를 순회해야 하므로 O(N)의 시간복잡도가 필요합니다.

4. 힙 생성 (Heapify)

정렬되지 않은 배열로부터 힙을 생성하는 과정도 중요합니다.

private void heapify() {
    final Object[] es = queue;
    int n = size, i = (n >>> 1) - 1;
    final Comparator<? super E> cmp;
    if ((cmp = comparator) == null)
        for (; i >= 0; i--)
            siftDownComparable(i, (E) es[i], es, n);
    else
        for (; i >= 0; i--)
            siftDownUsingComparator(i, (E) es[i], es, n, cmp);
}

처음에는 O(N log N)으로 보일 수 있지만, 실제로는 O(N)의 시간복잡도를 가집니다. 이는 리프 노드에 가까운 노드들은 매우 적은 비교만 필요하기 때문입니다.