[자료구조] 9. 힙(Heap)

힙(Heap)

힙은 완전 이진 트리(Complete binary tree)의 형태를 가집니다. 즉, 완전 이진 트리의 성질에 따라 트리의 높이 h <= log n 입니다.

힙의 특징은 가장 최상위 부모에 가장 우선순위가 높은 값이 배치되고, 모든 아래의 원소들은 자기 부모보다 우선순위가 낮아야 한다는 규칙을 따릅니다.

[이미지]

이러한 특징을 가지기에 힙에서는 무조건 우선순위가 높은값이 최상위에 있게 되고, O(1)에 접근이 가능하게 됩니다.

이때 원소의 값이 클수록 높은 우선순위를 가지는 힙을 최대힙, 작은 수록 높은 우선순위를 가지는 힙을 최소힙이라고 부릅니다.

 

힙을 설명하기 위해서 힙의 핵심이 되는 삽입과 삭제의 과정에 대해 아래에 설명합니다.

삽입

힙에 원소를 삽입할때는 다음 과정을 거칩니다.

[이미지]

1. 힙 마지막에 원소를 삽입한다(보통 완전 이진 트리를 배열로 구현하기에 배열의 마지막에 삽입합니다): O(1)

[이미지]

2. heapify(마지막 원소를 upheap) 한다: O(log n)

upheap

이때 upheap은 트리의 가장 아래레벨부터 위로 원소를 비교하며 올라가는 방식입니다.

과정은 다음과 같습니다.

1. 자신의 부모가 존재하지 않으면 종료한다.

2. 자신의 부모와 비교해 자신의 우선순위가 더 높으면 위치를 교환한다. 이후 반복

이 과정을 통해 O(h) == O(log n)시간에 heap 규칙에 맞게 만들 수 있습니다.

삭제

힙에서의 삭제는 다음과 같은 과정을 거칩니다. 이때 임의의 원소를 삭제할 수는 없고, 가장 상단에 있는 우선순위가 가장 높은 원소만을 삭제할 수 있습니다.

[이미지]

1. 최상위 노드의 위치와 최하위(마지막) 노드의 위치를 바꾼다: O(1)

2. 최하위로 간 노드를 삭제한다: O(1)

[이미지]

3. heapify(최상위 노드로부터 downheap) 한다: O(log n)

downheap

downheap은 트리의 가장 위에서부터 아래로 원소를 비교하며 내려가는 방식입니다.

1. 자신의 left, right자식과 비교하여 자신의 우선순위가 가장 높으면 종료한다.

2. 아니라면 자신의 left, right 자식중 우선순위가 더 높은 자식과 위치를 바꾼다. 이때 우선순위가 더 높은 자식과 바꾸는 이유는 낮은 자식과 바꾸면 한번더 바꾸어 줘야하는 비효율이 발생하기 때문입니다. 위 과정을 반복합니다.

이 과정을 통해 O(h) == O(log n) 시간에 heapify할 수 있습니다.

활용

힙은 주로 우선순위 큐의 구현을 위해 사용됩니다.

이런 O(log n)에 삽입/삭제 가능한 특성으로 인해 힙은 정렬에서도 사용할 수 있는데, 이때 n개의 원소를 정렬하면 n * O(log n)으로 O(n log n) 시간에 정렬이 가능합니다. 추가적으로 공간을 소모하지 않는 In-place heap sort 또한 가능합니다.

ADT

int getSize()
bool isEmpty()

// typename T
void insert(T& element): 원소를 삽입
T& removeMax(): 가장 우선순위가 높은 값을 반환하고 삭제
T& max(): 가장 우선순위가 높은 값을 반환

구현

힙은 완전 이진 트리 형태기에 배열로 구현하는것이 편리합니다.

아래는 C++로 작성된 최소힙의 예시입니다.

#include <iostream>
#include <vector>

using namespace std;

class MinHeap {
  private:
    vector<int> arr;
    void swap(int idx1, int idx2) {
        arr[0] = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = arr[0];
    }

  public:
    MinHeap() { arr.push_back(0); }
    int getSize() { return arr.size() - 1; }
    bool isEmpty() { return arr.size() == 1; }
    void insert(int e) {
        arr.push_back(e);
        upHeap(getSize());
    }
    int getMin() {
        if (isEmpty())
            return -1;
        return arr[1];
    }
    void removeMin() {
        if (isEmpty())
            return;

        swap(1, getSize());
        arr.pop_back();
        downHeap(1);
    }
    void upHeap(int idx) {
        if (idx == 1)
            return;
        int parent = idx / 2;
        if (arr[parent] > arr[idx]) {
            swap(parent, idx);
            upHeap(parent);
        }
    }
    void downHeap(int idx) {
        int left = 2 * idx;
        int right = 2 * idx + 1;
        int child;

        if (left > getSize())
            return;
        else if (left == getSize())
            child = left;
        else {
            if (arr[left] <= arr[right])
                child = left;
            else
                child = right;
        }
        if (arr[child] < arr[idx]) {
            swap(child, idx);
            downHeap(child);
        }
    }
};

힙을 배열로 구현할때 구현 편리성을 위하여 [0]번째 배열은 사용하지 않는데, 이를 원소들을 스위칭할때 임시 공간으로 활용할 수 있습니다.

Bottom-up heap construction

힙을 최초로 만들 때 빈 힙에 일일이 원소를 삽입하면 O(n log n)시간이 걸린다. 그러나 Bottom-up heap construction 방식을 사용하면 힙을 최초 구현할 때 O(n)으로 구현이 가능합니다.

효율

heap의 insert()와 delete()는 모두 O(log n)의 시간복잡도를 가집니다.