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

우선순위 큐(Priority Queue)

우선순위 큐(Priority Queue)는 일반적인 큐에 우선순위라는 개념을 추가한 것이다.
보통의 큐는 가장 먼저 들어온 입력이 먼저 나오지만, 우선순위 큐에서는 우선순위가 가장 높은 원소가 먼저 빠져나오게 된다.
이를 구현하기 위한 자료구조로 힙(Heap)이 있다.

힙(Heap)

힙이란 특별한 조건을 만족하는 완전 이진 트리이다.
완전 이진 트리란 자식이 최대 두개인 이진 트리 중에서 다음과 같은 조건을 만족하는 것이다.

• 맨 아래에서 3번째 레벨까지는 모두 자식 노드가 두개일 것
• 맨 아래 레벨은 왼쪽부터 순서대로 채워져있을 것

좀 더 쉽게 말하면, 맨 아래 레벨이 왼쪽부터 순서대로 채워져있고, 안 채워진 노드를 전부 채우면 포화 이진 트리가 되는 경우이다.

최대 힙이 만족해야 하는 조건은 아래와 같다.

• 완전 이진 트리일 것
• 모든 노드가 값을 가지며, 노드의 값은 자식노드들보다 크거나 같을 것

두번째 조건이 작거나 같다로 바뀐다면 최소 힙이라고 부른다.

배열과 완전 이진 트리

노드의 갯수가 고정되어 있을 때 만들 수 있는 완전 이진 트리는 단 한가지이다.
따라서, 임의의 배열을 완전 이진 트리로 해석할 수 있다.
a[i]의 자식 노드는 a[2i+1]과 a[2i+2]가 된다.
물론, 2i+1과 2i+2 중 원래 배열의 index가 될 수 없는 것이 있다면 그 자식 노드는 없는 것이다.

우선순위 큐의 최대 힙을 이용한 구현

우선순위 큐를 최대 힙으로 구현할 때 필요한 것은 크게 두 가지이다.

• 원소의 삽입
• 원소의 삭제

원소의 삽입

원소의 삽입을 구현하기 위해서는 힙의 맨 끝에 원소를 한 개 추가하고, 이를 최대 힙이 되도록 고쳐주는 과정이 필요하다.
이는 추가된 원소와 부모 노드를 교환하는 과정을 반복하는 식으로 구현할 수 있다.

원소의 삭제

우선순위 큐에서 원소를 삭제할 때는 항상 가장 큰 원소를 삭제하므로, 맨 위의 루트 노드가 삭제된다.
맨 위의 루트 노드를 삭제한 후 맨 마지막 노드를 루트 노드로 옮기고, 다시 최대 힙 조건을 만족하도록 고쳐주면 된다.
이는 루트 노드부터 내려오면서 부모-자식의 대소 관계가 맞지 않다면 두 노드를 교환하는 과정을 반복해주면 된다.