Heap, Priority Queue

Heap과 Priority Queue에 대해 설명하기 전에 완전 이진트리에 대해 알아보자.

완전 이진 트리

먼저, 이진 트리(binary tree)는 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조를 의미한다. 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다. 

 

완전 이진 트리는 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있다. 마지막 레벨 h에서 1부터 2ʰ - 1 개의 노드를 가질 수 있다. 완전 이진 트리는 배열을 사용해 효율적으로 표현 가능하다.

(A)의 경우 완전 이진 트리이고, (B)의 경우 아니다.

 

힙(Heap)

• 힙은 완전 이진 트리의 일종이다.
• 여러 값들 중 최댓값 혹은 최솟값을 빠르게 찾아내기 위한 자료구조이다.
• 힙은 중복된 값을 허용한다.
• Max Heap은 가장 큰 값을 빠르게 찾기 위한 것이고 Min Heap은 가장 작은 값을 빠르게 찾기 위한 것이다.

Max Heap(최대 힙)

Max Heap은 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리이다.

부모노드의 Key >= 자식 노드의 Key

 

Min Heap(최소 힙)

Min Heap은 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리이다.

부모 노드의 Key <= 자식 노드의 Key

Heap 구현

Heap이 완전 이진 트리이기 때문에 배열로 구현할 수 있다. 완전 이진 트리의 특성상 왼쪽부터 오른쪽으로 차곡차곡 노드가 저장되므로 배열의 구조를 사용할 수 있게 된다.

구현을 쉽게 하기 위해서 0번 index를 사용하지 않는다. index를 통해 노드를 접근할 수 있는데, 이를 다음과 같이 정리 할 수 있다.

• 부모노드의 index = (자식 노드의 index) / 2
• 왼쪽 자식 노드의 index = (부모 노드의 index) * 2
• 오른쪽 자식 노드의 index = (부모 노드의 index) * 2 + 1

Heap의 정의

typedef struct {
    int data[MAX_SIZE];
    int heap_size;
}Heap;

Heap* init(Heap* h) {
    h = (Heap*) malloc(sizeof(Heap));
    h->heap_size = 0;
    return h;
}   

Heap 의 삽입 

Heap의 삽입은 다음과 같은 과정을 거친다.

1. 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다. ( = 배열의 마지막에 원소를 추가한다.)
2. 새로운 노드를 부모 노드와 비교해서 교환해야 한다면 힙의 성질을 만족 할 때 까지 교환한다.

Max Heap의 예로 살펴보자.

첫 번째로 배열의 가장 마지막 위치에 새로운 원소 8을 추가한다. 

 

두 번째로 부모노드인 index 4번 노드와 키 값을 비교한다. 이때 자식 노드인 index 8번 노드가 키 값이 더 크므로 (8 > 4) 부모노드와 위치를 교환한다.

마지막으로 부모노드인 index 2번 노드와 키 값을 비교한다. 이 때 자식노드인 index 4번 노드가 키 값이 더 크므로 (8 > 7) 부모노드와 위치를 교환한다. 이렇게 하면 Max Heap의 성질을 만족하게 되고 삽입 과정이 종료된다.

 

Min Heap은 반대로 부모노드가 자식노드보다 작도록 교환하면 된다.

void push(Heap* h, int data) {
    h->heap_size++;
    h->data[h->heap_size] = data; // 맨 마지막에 새로운 데이터를 넣는다.

    int child = h->heap_size;
    int parent = child / 2; // 부모의 인덱스는 자식의 인덱스 / 2 한 값

    while (parent) {
        // 자식이 부모보다 크다면 위치를 교체해준다.
        if (h->data[parent] < h->data[child]) {
            int temp = h->data[parent];
            h->data[parent] = h->data[child];
            h->data[child] = temp;

            // 내 위치를 부모로 바꿔주고 새로운 부모 인덱스를 가져온다.
            child = parent;
            parent = child / 2;
        }
        // 만약 부모가 더 크다면 종료.
        else {
            break;
        }
    }
}

위의 코드를 아래와 같이 실행시켜보면 결과값은 23 9 1 3 5 가 출력되며 아래 그래프처럼 구성됨을 알 수 있다.

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    Heap* h = NULL;
    h = init(h);
    push(h, 3);
    push(h, 5);
    push(h, 1);
    push(h, 23);
    push(h, 9);
    for (int i = 1; i <= h-> heap_size; i++) {
        printf("%d ", h->data[i]);
    }

    return 0;
}

트리를 살펴보면 MAX HEAP을 만족함을 알 수 있다.

Heap 의 삭제

위의 Max Heap에서 한 원소를 삭제하는 과정을 알아보자.

Max Heap에서 삭제는 가장 큰 값을 반환하고 그 값을 힙에서 제거한다. 이후, 가장 마지막에 있는 값을 맨 위로 올린 다음 아래로 내려가면서 자리를 찾아간다. 아래로 내려갈 때, 왼쪽과 오른쪽 자식 중 큰 값과 비교한다. 이는 자식의 인덱스 번호가 전체 heap 크기 이하이거나 부모가 자식보다 작을 때 반복한다.

int empty(Heap* h) {
    // heap size가 0이면 1 반환
    return (h->heap_size ? 0 : 1);
}
int pop(Heap* h) {
    int res = h->data[1];
    h->data[1] = h->data[h->heap_size]; // 맨 마지막 데이터를 맨위로 올린다음
    h->heap_size--;

    int parent = 1;
    int child = 2;

    // 자식의 인덱스가 힙 크기보다 작거나 같으면 반복
    while (child <= h->heap_size) {

        if (child + 1 <= h->heap_size && h->data[child] < h->data[child + 1]) {
            child++;
        }

        if (h->data[parent] < h->data[child]) {
         int temp = h->data[child];
         h->data[child] = h->data[parent];
         h->data[parent] = temp;

         // 내 위치를 바꾼 인덱스 위치로
         parent = child;
         child = parent * 2;
        }
        else {
            break;
        }
    }
    return res;
}

아래의 코드를 돌려보면 결과는 23 9 5 3 1이 나오게 된다.

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    Heap* h = NULL;
    h = init(h);
    push(h, 3);
    push(h, 5);
    push(h, 1);
    push(h, 23);
    push(h, 9);

    while (!empty(h)) {
        printf("%d ", pop(h));
    }
    return 0;
}

Min Heap은 부등호만 반대로 해주면 구현 가능하다.

Priority Queue

우선순위 큐는 '우선 순위'를 가진 데이터들을 저장하는 큐를 의미한다.

데이터를 꺼낼 때 우선 순위가 높은 데이터가 먼저 나온다는 특징을 가지고 있다. 시간복잡도 : O(NlogN)

일반적으로 우선순위 큐는 최대 힙(Max Heap)을 이용해 구현한다.

 

위에서 설명한 것처럼, 최대 힙은 부모 노드가 자식 노드보다 값이 큰 완전 이진 트리를 의미한다.

전체 트리에서 루트 노드가 가장 큰 값을 가진다.

 

Priority Queue 구현

#define MAX_SIZE 100000
typedef struct{
    int heap[MAX_SIZE];
    int heap_size;
}priorityQueue;

priorityQueue* init(priorityQueue* pq) {
    pq = (priorityQueue*) malloc(sizeof(priorityQueue));
    pq->heap_size = 0;
    return pq;
}
void push(priorityQueue* pq, int data) {
    pq->heap_size++;
    pq->heap[pq->heap_size] = data;

    int child = pq->heap_size; // 자식의 위치는 마지막 인덱스
    int parent = child / 2;

    while (parent) {

        if (pq->heap[parent] < pq->heap[child]) {
            int temp = pq->heap[parent];
            pq->heap[parent] = pq->heap[child];
            pq->heap[child] = temp;


            child = parent;
            parent = child / 2;
        }
        else {
            break;
        }
    }
}
int empty(priorityQueue *pq) {
    return (pq->heap_size ? 0 : 1);
}

int pop(priorityQueue* pq) {
    int res = pq->heap[1];
    pq->heap[1] = pq->heap[pq->heap_size];
    pq->heap_size--;

    int parent = 1;
    int child = 2;

    while (child <= pq->heap_size) {
     if (child + 1 <= pq->heap_size && pq->heap[child] < pq->heap[child + 1]) {
         child++;
     }

     if (pq->heap[parent] < pq->heap[child]) {
        int temp = pq->heap[child];
        pq->heap[child] = pq->heap[parent];
        pq->heap[parent] = temp;

        parent = child;
        child = parent * 2;
     }
     else {
         break;
     }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    priorityQueue* pq = NULL;
    pq = init(pq);
    push(pq, 3);
    push(pq, 5);
    push(pq, 1);
    push(pq, 23);
    push(pq, 9);

    while (!empty(pq)) {
        printf("%d ", pop(pq)); // 23 9 5 3 1
    }
    return 0;
}