[Data Structure] #우선순위 큐(Priority Queue)

우선순위 큐는 우선 순위라는 개념을 큐에 도입한 자료구조입니다.

구현하는 방법

우선순위를 구현하는 방법은 여러 가지가 있습니다. 배열, 연결 리스트, 힙을 이용합니다. 그 중에서도 오늘은 힙을 활용해 보겠습니다.

힙?

힙은 우선순위 큐를 위해 만들어진 자료구조로 느슨한 정렬 상태를 가지고 있습니다. 삽입, 삭제연산의 시간복잡도는 O(logN)입니다.

• 힙은 완전 이진 트리입니다.
• 최대 힙의 경우, 부모 노드 key >= 자식 노드 key
• 최소 힙의 경우, 부모 노드 key <= 자식 노드 key

힙은 완전 이진 트리이기 때문에 차례대로 번호를 붙일 수 있으며 이를 인덱스로 하는 배열에 노드들을 저장합니다. 물리적인 자료구조는 배열입니다.

삽입 연산

노드를 삽입할 때는 무조건 leaf노드 위치부터 시작합니다. 부모 노드와 key를 반복적으로 비교합니다.

• leaf노드로 먼저, 삽입한다.
• 부모노드와(index / 2) 비교하여, 최대힙의 경우 부모노드가 더 작으면 끌어내리고 최소 힙의 경우 부모 노드가 더 크면 끌어내립니다.
• 각각의 조건을 만족하면 더 이상 끌어내리지 않습니다.

삭제 연산

최대 힙의 경우, 삭제할 경우 루트 노드가 삭제됩니다. 말단 노드를 루트 노드의 위치로 가져오며, 이 후에는 자식노드와 말단노드를 반복적으로 비교하며 조건을 만족할때까지 끌어내립니다.

코드 구현

#include <stdio.h>
#include <stdlib.h>

#define MAX_ELEMENT 200

typedef struct {
  int key;
} element;

typedef struct {
  element heap[MAX_ELEMENT]; // 힙은 1차원 배열로 표현될 수 있다.
  int heap_size;
} HeapType;

HeapType* create() {
  return (HeapType*)malloc(sizeof(HeapType));
}

void init(HeapType *h) {
  h->heap_size = 0;
}

/**
 * 삽입연산
 * 1. 말단 노드의 인덱스를 구합니다.
 * 2. 배열이 빈 경우를 validation하고, 부모의 key값과 비교를 하여 부모의 값이 더 작으면 부모를 끌어내립니다.
 * 3. 반복문을 돌며, 부모의 값이 더 큰 경우 지금 인덱스의 요소에 값을 삽입하고 종료합니다.
 */
void insert(HeapType *h, element item) {
  int i;
  i = ++(h->heap_size); // 새로 삽입되게 될 노드의 부모를 찾기 위해 미리 1을 더해준다.

  while((i != 1) && (item.key > h->heap[i / 2].key)) { // 부모 노드의 인덱스는 2로 나눠준 정수값이다.
    h->heap[i] = h->heap[i / 2];
    i /= 2;
  }
  h->heap[i] = item; // 부모 노드가 더 크면 그 자리에 item의 키값을 삽입한다.
}

/**
 * 삭제연산 (max heap)
 * 1. 루트노드를 삭제합니다.
 * 2. 말단노드를 루트노드로 가져옵니다.
 * 3. 반복문을 돌며, 자식과 값을 비교해서 자식의 값이 더 큰 경우 자식을 끌어올립니다.
 * 4. 더이상 큰 자식노드가 없을 경우, 지금 인덱스 요소에 값을 삽입하고 종료합니다.
 */
element delete(HeapType *h) {
  element rootNode = h->heap[1];

  element leafNode = h->heap[h->heap_size--];

  int parent, child;

  parent = 1;
  child = 2;

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

    if (leafNode.key >= h->heap[child].key) break;

    h->heap[parent] = h->heap[child];
    parent = child;
    child *= 2;
  }

  h->heap[parent] = leafNode;
  return rootNode;
}

int main(void) {
  element e1 = {10}, e2 = {5}, e3 = {30};
  element e4, e5, e6;
  HeapType *heap;

  heap = create();
  init(heap);

  insert(heap, e1);
  insert(heap, e2);
  insert(heap, e3);

  e4 = delete(heap);
  printf("< %d >", e4.key);

  e5 = delete(heap);
  printf("< %d >", e5.key);

  e6 = delete(heap);
  printf("< %d >", e6.key);

  free(heap);
  return 0;
}