[자료구조] 우선순위 큐와 힙

반응형

 

우선순위 큐(Priority Queue)

우선순위 큐의 큐는 먼저 들어온 데이터가 먼저 나가는, 그 큐가 맞다. 둘의 차이점이라면, 우선순위 큐는 우선순위가 높은 데이터가 먼저 출력되는 것이 차이다. 아래와 같은 배열이 있다고 하자.

Array arr[10] = { 1, 3, 4, 9, 6, 2, 7, 8, 10, 5 };
Priority_Queue pq[10];

이 배열을 우선순위 큐(pq)에 저장된다고 하자. 큰 수에 우선순위가 주어진다고 하면, pq에는 아래와 같이 저장된다.

Priority_Queue pq[10] = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };

입력은 1, 3, 4, ..., 10, 5 순으로 되었지만, 우선순위 큐에는 큰 수부터 나열되어있다. 즉, 높은 우선순위가 앞에 위치한 상태이다.

 

우선순위 큐는 먼저 삭제되는 요소가 어떤 우선순위를 갖는지에 따라서 최대 우선순위 큐와 최소 우선순위 큐로 나뉜다. 최대 우선순위 큐는 우선순위가 가장 높은 요소를 먼저 삭제하는 것이다. 최소 우선순위 큐는 반대로 우선순위가 가장 낮은 요소가 먼저 삭제되는 것이다.

 

우선순위 큐 구현

우선순위 큐는 앞에서 했던 방법들과 같이 배열과 연결 리스트, 이번에 배우게 될 힙을 이용해서 구현할 수 있다. 하지만, 힙에 비해 나머지 둘은 효율적이지 않은데, 그 이유를 살펴보자.

 

배열을 이용한 구현

정렬된 배열
정렬된 배열이면 삽입 연산의 경우 새로운 요소가 들어갈 공간을 찾아야 하고, 그 공간을 비워주고 하나씩 자리를 이동시켜야한다. 때문에 \(\Theta(n)\)의 시간 복잡도가 된다. 삭제는 가장 뒤의 요소를 삭제하면 되므로 \(\Theta(1)\)이 된다.

정렬이 되지 않은 배열
이 경우에는 삽입은 신경쓸 필요가 없으므로 \(\Theta(1)\)이 된다. 하지만, 삭제의 경우에는 요소를 찾는 과정과 삭제 후 빈자리를 채워주는 과정이 필요하다. 때문에 \(\Theta\)의 시간 복잡도가 된다.

 

연결리스트를 이용한 구현

정렬된 연결 리스트
정렬이 되어있는 상태라면, 첫 번째 노드를 삭제하기만 하면 되므로 \(\Theta(1)\)이다. 하지만, 삽입의 경우에는 모든 연결 노드들을 비교해보며 삽입 위치를 정해야 하므로 \(\Theta(n)\)이 된다.

정렬이 되지 않은 연결 리스트
삽입할 때 처음에 삽입해버리면 \(\Theta(1)\)이 된다. 하지만 삭제를 하려면 모든 노드들을 방문하면서 삭제할 노드를 찾아야 하므로 \(\Theta(n)\)이 된다.

 

결과적으로 둘의 시간 복잡도는 \(\Theta(n)\)이 된다. 힙의 경우는 삽입과 삭제의 시간 복잡도가 \(\Theta(logn)\)이다. 즉, 힙이 절대적으로 유리하다는 것이 보인다.

 

[참고] 시간 복잡도

[알고리즘] 알고리즘

힙(Heap)

힙은 완전 이진트리 기반의 자료 구조로, 항상 부모 노드의 키 값은 자식 노드의 키 값보다 큰(또는 작은) 완전 이진 트리이다. 힙 트리라고도 한다. 우선 순위 큐와 마찬가지로 힙도 최대 힙(max heap)과 최소 힙(max heap)으로 나뉜다. 최대 힙은 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리이다. 반대로 최소 힙은 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리이다.

각각 최대 힙(좌), 최소 힙(우)

 

 

힙 구현

힙은 완전 이진 트리이므로 이에 적합한 방식인 배열을 이용해 구현을 해보자. 트리를 구현할 때와 같이, 각 노드에서의 자식과 부모 노드의 인덱스는 다음과 같은 방법으로 구할 수 있다.

한 노드의 인덱스가 i일 때,
부모 노드의 인덱스 = i / 2
왼쪽 자식 노드의 인덱스 = 2 * i
오른쪽 자식 노드의 인덱스 = 2 * i + 1

#include <iostream>
#include <cstdlib>

const int MAX_HEAP = 16;

class Heap {
    int heap[MAX_HEAP];
    int hsize;

    int parent(int i) { return heap[i / 2]; }
    int left(int i) { return heap[i * 2]; }
    int right(int i) { return heap[i * 2 + 1]; }

public:
    Heap() { init(); }
    ~Heap() {}
    void init() { hsize = 0; }
    bool is_empty() { return hsize == 0; }
    bool is_full() { return hsize == MAX_HEAP - 1; }
    int find() { return heap[1]; } // 루트 노드
};

전반적인 구성은 완전 이진 트리를 구현했을 때와 비슷하다. 삽입 연산과 삭제 연산을 더 고려해주면 된다.

 

삽입 연산(insert)

힙이 최소 힙이든, 최대 힙이든 그 힙의 성질에 맞도록 노드를 삽입시켜야 한다. 아래는 최대 힙에 9를 삽입했을 때를 나타낸 것이다.

위의 과정을 풀어 써보자.

1. 9를 마지막 자리에 삽입한다.
2. 부모 노드인 5보다 크므로 둘의 위치를 바꾼다.
3. 부모 노드인 8보다 크므로 둘의 위치를 바꿔준다.
4. 부모 노드인 11보다 작으므로 교환을 멈춘다.

void insert(int value) {		
    int i;
    
    if (is_full()) {
        cout << "힙 포화 상태" << endl;
        exit(1);
    }
    
    hsize++;
    for (i = hsize; i != 1 && value > parent(i); i /= 2) {
        heap[i] = parent(i);
    }
    heap[i] = value;
}

삭제 연산(remove)

힙에서의 삭제는 우선 순위가 가장 높은 노드인 루트 노드를 삭제하는 것이다. 루트가 사라지면서 생긴 공백은 가장 마지막의 노드로 채운 뒤, 힙의 성질에 맞도록 강등시켜 나가면 된다.

위의 과정을 풀어 써보자.

1. 11과 1의 위치를 바꾼다.
2. 자식 노드인 9보다 작으므로 위치를 바꾼다.
3. 자식 노드인 8보다 작으므로 위치를 바꾼다.

int remove() {
    int root, last, parent = 1;

    if (is_empty()) {
        cout << "힙 공백 상태" << endl;
        exit(1);
    }
    
    root = heap[1];
    last = heap[hsize];
    hsize--;

    for (int child = 2; child <= hsize; child *= 2) { // 왼쪽 자식노드부터 검사
        if (child < hsize && left(parent) < right(parent)) { 
            child++; // 오른쪽 자식노드가 더 크면 인덱스에 + 1을 해줘서 오른쪽 자식노드가 올라온다.
        }

        if (last >= heap[child]) {
            break;
        }
        heap[parent] = heap[child];
        parent = child;
    }
    heap[parent] = last;
    return root;
}

전체 코드

#include <iostream>
#include <cstdlib>

const int MAX_HEAP = 16;

class Heap {
    int heap[MAX_HEAP];
    int hsize;

    int parent(int i) { return heap[i / 2]; }
    int left(int i) { return heap[i * 2]; }
    int right(int i) { return heap[i * 2 + 1]; }

public:
    Heap() { init(); }
    ~Heap() {}
    void init() { hsize = 0; }
    bool is_empty() { return hsize == 0; }
    bool is_full() { return hsize == MAX_HEAP - 1; }
    int find() { return heap[1]; } // 루트 노드

    // 삽입
    void insert(int value) {		
        int i;
        hsize++;
        for (i = hsize; i != 1 && value > parent(i); i /= 2) {
            heap[i] = parent(i);
        }
        heap[i] = value;
    }

    // 삭제
    int remove() {
        int root, last, parent = 1;

        root = heap[1];
        last = heap[hsize];
        hsize--;

        for (int child = 2; child <= hsize; child *= 2) { // 2의 배수이므로 왼쪽 자식노드부터 검사
            if (child < hsize && left(parent) < right(parent)) { // 오른쪽 자식노드가 더 크면 인덱스에 + 1
                child++;
            }

            if (last >= heap[child]) {
                break;
            }
            heap[parent] = heap[child];
            parent = child;
        }
        heap[parent] = last;

        return root;
    }

    // 힙 출력
    void print() {
        for (int i = 1, level = 1; i <= hsize; i++) {
            if (i == level) {
                cout << endl;
                level *= 2;
            }
            cout << heap[i] << " ";
        }
        cout << endl << "-----------------------" << endl;
    }
};

 

힙 정렬(Heap Sort)

 

정렬 알고리즘에는 힙 정렬이라는 알고리즘이 있다. 힙 정렬의 힙이 바로 이 힙을 뜻한다.

[참고] 힙 정렬​

[알고리즘] 정렬(2) - 병합 정렬, 퀵 정렬, 힙 정렬

 

 

[Reference]

http://www.kyobobook.co.kr/product/detailViewKor.laf?ejkGb=KOR&mallGb=KOR&barcode=9788970509419&orderClick=LAG&Kc= 

자료구조 - 교보문고

 

 

728x90