1. 우선순위 큐
우선순위 큐는 추상 자료형(abstract data type, ADT)으로 구현 방법이나 연산의 시간 복잡도 등을 정의하고 있지 않습니다.
흔히 "우선순위 큐"는 "힙"이라고 오해하는 경우가 있으나 "힙"은 "우선순위 큐"라는 추상 자료형을 구현한 "자료구조"에 해당합니다.
우선순위 큐는 선입선출(Fisrt In First Out, FIFO)인 큐와 다르게 우선순위가 더 높은 원소가 먼저 나갑니다.
예를 들어 크기가 큰 것이 높은 우선순위를 가지는 우선순위 큐가 있다고 해봅시다.
1, 3, 2가 어떤 순서로 들어와도, 나갈 때는 우선순위가 높은 3, 2, 1 순으로 나가게 됩니다.
그림에서는 우선순위 큐에 원소가 들어올때마다 정렬이 일어나는 것으로 보여주고 있습니다만,
우선순위 큐에 들어올 때 정렬이 되든, 나갈 때 우선순위를 확인해 가장 우선인 원소를 내보내든 상관 없습니다.
https://ko.wikipedia.org/wiki/우선순위_큐
우선순위 큐 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 컴퓨터 과학에서, 우선순위 큐(Priority queue)는 평범한 큐나 스택과 비슷한 축약 자료형이다. 그러나 각 원소들은 우선순위를 갖고 있다. 우선순위 큐에서, 높은
ko.wikipedia.org
2. 힙(Heap)
힙은 1964년에 J.W.J. Williams가 힙 정렬과 함께 발표한 자료구조입니다.
힙은 완전이진트리(Complete Binary Tree)를 이용하여 가장 큰 우선순위를 가지는 값을 루트에 효율적으로 위치시킬 수 있게 합니다.
힙은 항상 부모가 자식보다 큰 우선순위를 가지는 값을 지니지만, 형제 간에는 이를 확인하지 않습니다.
루트 노드는 단 하나이므로, 루트 노드의 값이 가장 큰 우선순위를 가지게 됩니다.
이런 느슨한 정렬 상태를 이용해 \(O(\log{n})\) 시간만에 원소의 삽입과 삭제를 가능하게 합니다.
따라서 힙은 우선순위 큐를 구현하는데 보편적으로 이용되고 있습니다.
가. 배열로 완전이진트리 구현하기
배열은 인덱스를 이용해 값에 접근하는 동작이 효율적(\(O(1)\))입니다.
완전이진트리의 자식에서 부모로, 부모에서 자식으로 빠르게 탐색할 수 있도록 배열과 인덱스를 가지고 구현할 수 있습니다.
(세그먼트 트리에 대한 글에서 완전이진트리를 배열로 구현하는 것을 정리했었습니다.)
https://kimwooil.tistory.com/416
[416] 세그먼트 트리의 개념
1. 세그먼트 트리영어 단어 segment는 분할, 구간, 분절 등의 뜻을 지니고 있습니다.알고리즘에서 세그먼트 트리는 여러 값을 가지는 리스트의 특정 구간의 정보를 이진 트리 형태로 관리하는 자료
kimwooil.tistory.com
배열의 인덱스 0은 비워둡니다.(사용하지 않습니다.)
인덱스 1이 루트 노드입니다.
임의의 부모의 인덱스를 n이라고 했을 때, 자식의 인덱스는 n*2 와 (n*2)+1 로 바로 접근이 가능합니다.
임의의 자식의 인덱스를 n이라고 했을 때, 부모의 인덱스는 n//2 로 바로 접근이 가능합니다.
나. 원소 추가
힙에 원소를 추가할 때에는 먼저 배열의 맨 뒤에 추가를 하고 시작합니다.
완전이진트리에서는 마지막 leaf 노드가 추가되는 것과 같습니다.
이후 추가된 노드로부터 root 노드까지 부모 노드를 거슬러 올라가며 힙의 성질(부모 노드가 우선순위가 더 큼)을 유지하도록 swap합니다.
과정이 상향식으로 진행되기 때문에 이 과정을 Sift-up 또는 Upheap 이라고 부릅니다.
시간 복잡도는 최악의 경우 트리의 높이만큼 swap이 일어나기 때문에 \(O(\log{n})\)입니다.
위 힙에서 16이 추가되는 과정을 그림으로 살펴봅시다.
heap = [0, 28, 13, 17, 3, 6, 11, 8]
def sift_up(i):
if i <= 1: # 부모 노드까지 올라온 경우 탈출
return
if heap[i] > heap[i//2]: # 힙의 성질이 깨진 경우
heap[i], heap[i//2] = heap[i//2], heap[i] # swap
sift_up(i//2) # 재귀적으로 부모 노드로 올라가며 다시 실행
def heappush(num): # 원소를 추가하는 함수
heap.append(num) # 완전이진트리의 제일 마지막 leaf 노드에 원소 추가
sift_up(len(heap)-1)
heappush(16)
print(heap)
# [0, 28, 16, 17, 13, 6, 11, 8, 3]다. 원소 삭제
힙에서 원소를 삭제할 때에는 가장 우선순위가 큰 root 노드가 삭제되어야 합니다.
이를 위해 먼저 배열의 1번 값(완전이진트리의 root)과 제일 마지막 값(완전이진트리의 마지막 leaf 노드)을 바꾸고 제일 마지막 값을 반환하면서 삭제합니다.
이후 root 노드에서 leaf 노드까지 자식 노드를 차례로 탐색해 내려가며 힙의 성질(부모 노드가 우선순위가 큼)을 유지하도록 swap합니다.
이때 상향식과는 다르게 두 자식 노드와 모두 비교해보아야 힙의 성질이 유지가 됩니다.
과정이 하향식으로 진행되기 때문에 이 과정을 Sift-down 또는 Downheap 이라고 부릅니다.
시간 복잡도는 상향식과 마찬가지의 이유로 \(O(\log{n})\)입니다.
위 힙에서 원소를 삭제하는 과정을 그림으로 살펴봅시다.
heap = [0, 28, 16, 17, 13, 6, 11, 8, 3]
def sift_down(i, length):
mx = i
left, right = i*2, (i*2)+1 # 두 자식의 인덱스
# 두 자식과 관계를 살펴 힙의 성질이 깨지는지 확인
if left < length and heap[left] > heap[mx]:
mx = left
if right < length and heap[right] > heap[mx]:
mx = right
if heap[i] != heap[mx]: # 힙의 성질이 깨졌다면,
heap[i], heap[mx] = heap[mx], heap[i] # 해당 자식과 swap
sift_down(mx, length) # 재귀적으로 내려가며 다시 실행
def heappop():
heap[1], heap[-1] = heap[-1], heap[1] # 완전이진트리의 root와 제일 마지막 leaf 를 swap
print(heap.pop()) # 원래 root 노드를 버리면서 출력
sift_down(1, len(heap))
heappop()
# 28
print(heap)
# [0, 17, 16, 11, 13, 6, 3, 8]힙에서 원소를 추가하고, 삭제할 때 어떤 과정을 거치는지 알아보았습니다.
이제 힙이 아닌 배열을 힙으로 만들려면 어떻게 해야할까요?
방법은 앞에서 살펴본 것처럼 Sift-up 또는 Sift-down 과정을 모든 노드로부터 반복하면 됩니다.
이제 힙 만드는 방법을 살펴봅시다.
라. 힙 만들기(Sift-up)
Sift-up을 활용한 힙 만들기 방법은 root 노드까지 부모 노드를 거쳐 올라가므로 root 노드를 제외하고 실행하면 됩니다.
순서는 root 노드의 왼쪽 자식부터 마지막 leaf 노드 순서로 진행합니다.
배열에서는 인덱스 2(root 노드의 왼쪽 자식)부터 차례대로 마지막 원소까지 진행합니다.
그 이유는 상향식으로 swap이 일어나기 때문에 올바른 힙을 구성하려면 이미 자신으로부터 root 노드까지 정렬이 이루어져있어야 합니다.
하지만 역순으로 진행할 경우, 자신으로부터 root 노드까지 정렬이 안 되어 있을 경우 올바른 힙이 구성되지 않습니다.
이제 Sift-up으로 힙을 만드는 과정을 살펴봅시다.
위와 같은 힙이 아닌 배열이 있을 때, Sift-up으로 힙을 만드는 과정은 다음 그림과 같습니다.
모든 과정을 거치고 나면 다음과 같은 힙이 완성됩니다.
nums = [0, 6, 2, 17, 31, 7, 12, 19]
def sift_up(i):
if i <= 1:
return
if nums[i] > nums[i//2]:
nums[i], nums[i//2] = nums[i//2], nums[i]
sift_up(i//2)
def heapify():
for i in range(2, len(nums)):
sift_up(i)
heapify()
print(nums)
# [0, 31, 17, 19, 2, 7, 6, 12]
마. 힙 만들기(Sift-down)
Sift-down 방법은 leaf 노드까지 내려가므로 leaf 노드들을 제외하고 실행하면 됩니다.
순서는 마지막 leaf 노드의 부모 노드부터 root 노드까지 역순으로 진행합니다.
배열에서는 인덱스 n//2(마지막 leaf 노드의 부모노드)부터 역순으로 인덱스 1(root 노드)까지 진행합니다.
그 이유는 Sift-up과 반대로 이해하면 됩니다.
이제 Sift-down으로 힙을 만드는 과정을 살펴봅시다.
Sift-down으로 위 배열을 힙으로 만드는 과정은 다음과 같습니다.
모든 과정을 거치고 나면 다음과 같은 힙이 완성됩니다.
nums = [0, 6, 2, 17, 31, 7, 12, 19]
def sift_down(i, length):
mx = i
left, right = i*2, (i*2)+1
if left < length and nums[left] > nums[mx]:
mx = left
if right < length and nums[right] > nums[mx]:
mx = right
if nums[i] != nums[mx]:
nums[i], nums[mx] = nums[mx], nums[i]
sift_down(mx, length)
def heapify():
length = len(nums)
for i in range((len(nums)-1)//2, 0, -1):
sift_down(i, length)
heapify()
print(nums)
# [0, 31, 7, 19, 2, 6, 12, 17]
바. 힙 만들기 시간 복잡도 비교
결론부터 이야기하자면 Sift-down을 활용한 방식은 \(O(n)\) 시간 복잡도를 가지고, Sift-up을 활용한 방식은 \(O(n\log{n})\)의 시간 복잡도를 가집니다.
따라서 힙을 만들 때에는 Sift-down을 사용하는 것이 더 효율적입니다.
Sift-up이 \(O(n\log{n})\)의 시간 복잡도를 가지는 이유는 직관적으로 이해가 됩니다.
\(O(\log{n})\)의 시간 복잡도를 가지는 Sift-up을 n번(정확히는 root를 제외한 n-1번) 반복하므로, 시간 복잡도는 \(O(n\log{n})\)이 됩니다.
하지만 Sift-down의 시간 복잡도가 \(O(n)\)인 것은 쉽게 이해가 되지 않습니다.
\(O(\log{n})\)의 시간 복잡도를 가지는 Sift-down을 leaf 노드를 제외하고 n/2번 반복하므로, 시간 복잡도는 \(O(\frac{n}{2}\log{n})\)이 될 것 같습니다.
하지만 잘 생각해보면 완전이진트리는 자식으로 내려갈수록 노드의 개수가 2배씩 증가합니다.
그리고 특정 노드에서 leaf 노드까지의 깊이까지만 swap이 일어나므로, 자식으로 내려갈수록 Sift-down의 효율성은 올라갑니다.
따라서 결과적으로 Sift-down의 시간 복잡도는 \(O(n\log{n})\)이 아닌 \(O(n)\)이 됩니다.
수식으로 살펴보면 다음과 같습니다.
\(\sum\limits_{i=1}^{\log {n}} \frac{n}{2^i} \cdot i = n \cdot \sum\limits_{i=1}^{\log{n}} \frac{i}{2^i} = n\cdot \left( \frac{1}{2^1} + \frac{2}{2^2} + \frac{3}{2^3} + \cdots + \frac{\log{n}}{2^{\log{n}}}\right) = O(n)\)
여기서 \(i\)는 해당 노드에서 leaf 노드까지의 깊이(Sift-down에서 swap되는 횟수)이고, 따라서 \(\frac{n}{2^i}\)는 해당 깊이 \(i\)에 존재하는 노드의 개수입니다.
