[자료구조] Heap & Priority Queue 구현

Priority_queue

Heap성질을 가진 자료구조입니다. 

 

Java에서 priority_queue 의 기본 정렬 구현은 Min Heap입니다.

C++에서 priority_queue 의 기본 정렬 구현은 Max Heap입니다.

 

Heap

힙(Heap) 은 특정 연산을 빠르게 수행하기 위한 이진 트리 자료구조로 부모 노드와 자식 노드간의 일련의 규칙을 통해 일관성있는 결과를 도출해내기 위한 자료구조입니다.

 

Min Heap은 부모가 자식보다 작은 이진 트리를 구성하여 루트 노드가 전체 데이터의 최솟값이 됩니다.

Max Heap은 부모가 자식보다 큰 이진 트리를 구성하여 루트 노드는 전체 데이터의 최댓값이 됩니다.

 

Binary Heap 구현은 이진 트리의 Root노드부터 단일 Leaf노드까지의 순회 비용만 가짐으로 push, pop 연산은 O(logN)의 복잡도를 가집니다.

Min/Max Heap 기능적 Heap을 구현하는 경우 top의 시간 복잡도는 O(1) 로 아주 효율적입니다.

하지만, priority_queue에 저장되어 있는 특정 요소를 찾으려고 하면 O(N)으로 비효율적입니다. 특정 요소를 찾기위한 자료 구조를 사용하고 싶다면 priority_queue말고 다른 자료구조(vector)를 사용해야 합니다. 

 

push

Heap에 새로운 원소가 삽입되는 경우 Heap의 마지막 위치(Leaf Node)에 값을 넣고 Root Node까지 올라오면서 맞는 위치를 찾습니다.

Min / Max Heap 조건에 만족한다면 해당 위치에 멈추고, 만족하지 않아 상위 노드로 가야한다면 부모 노드와 swap합니다. 자매 노드(Siblings)를 고려하지 않고 부모 노드만 고려하면 되기 때문에 O(logN) 시간 복잡도를 가집니다. 

즉, 빠르게 push연산이 가능합니다.

이진 트리로 표현하면 아래와 같습니다.

pop

Heap에 원소가 제거(삭제)되는 경우 마지막 노드가 루트 노드 위치에 오도록 변경합니다.

원소가 제거된 이후 루트 노드에서부터 하향식으로

(더 작은 자식 노드로) Heapify를 진행합니다.

부모 노드만 비교 연산을 하여 Min / Max Heap 조건에 만족한다면 해당 위치에 멈추고, 아니면 부모 노드와 swap합니다.

부모 노드만 고려하면 되기 때문에 pop연산도 O(logN)의 시간 복잡도로 힙 성질을 가집니다.

 

코드

Min Heap을 구현한 코드입니다.

int tree[1501] = { 0, };
int root = 0;
void myPush(int value)
{
    int cur = root;
    tree[root++] = value;
    while (cur > 0)
    {
        int parent = (cur - 1) / 2;
        if (tree[parent] > tree[cur]) {
            swap(tree[parent], tree[cur]);
        }
        else {
            break;
        }
        cur = parent;
    }
}
int myPop()
{
    int ret = tree[0];
    tree[0] = 1e8;
    swap(tree[0], tree[--root]);
    int cur = 0;
    while (2 * cur + 2 <= root)
    {
        int left = 2 * cur + 1;
        int right = 2 * cur + 2;
        int next = tree[left] < tree[right] ? left : right;
        if (tree[next] < tree[cur])
        {
            swap(tree[next], tree[cur]);
            cur = next;
        }
        else
        {
            break;
        }
    }
    return ret;
}

int main(int argc, char** argv)
{
    myPush(5);
    myPush(7);
    myPush(1);
    myPush(3);

    int a = myPop();
    int b = myPop();
    int c = myPop();
    int d = myPop();

    cout << a << " " << b << " " << c << " " << d << " ";

	return 0;
}

1 3 5 7