아래 포스트는 Data Structure and Algorithmic Thinking with Python을 참고하여 작성되었습니다.
1) Priority Queue(우선순위 큐)
1-1. What is a Priority Queue?
Priority Queue(이하 우선순위큐)는 Insert, DeleteMin(혹은 DeleteMax) 연산을 지원하는 추상적인 개념의 자료구조입니다.
무슨 말이냐 하면 어떤 자료구조(클래스)가 Insert, DeleteMin 연산을 가지고 있기만 하면 어떤 방식을 통해서 구현되었든 간에 우선순위큐로 불릴 수 있는 것입니다.
예를 들어서, Singly Linked List 클래스에서 몇 개의 메소드를 추가해서 우선순위큐처럼 만들 수도 있습니다.
- DeleteMin : head에서 tail까지 탐색하면서 최대인 값을 찾고 제거한다.
- Insert : head 앞에 새로운 노드를 추가한다.
이렇게 하면 Insert 기능은 O(1)으로 빠르지만 DeleteMin은 물론 Min을 찾는 작업조차도 O(n)으로 매우 느릴 것입니다.
이처럼 다른 자료구조로도 우선순위큐를 구현할 수 있는데요, 각각의 자료구조로 부터 구현한 우선순위큐의 성능은 다음과 같습니다.
| Implementation | Insertion | Deletion | Find Min |
|---|---|---|---|
| BST | logn (average) | logn (average) | logn (average) |
| AVL Tree | logn | logn | logn |
| Binary Heaps | logn | logn | 1 |
| Ordered list | n | 1 | 1 |
| Unordered list | 1 | n | n |
표를 보시면 처음 보는 듯한 Binary Heaps 를 통해서 우선순위큐를 구현할 때 성능이 가장 좋음을 확인할 수 있습니다.
그 Binary Heaps가 무엇인지는 밑에서 알아보도록 하겠습니다.
1-2. 왜 하필 Priority “Queue” ?
그런데 왜 이러한 구조가 하필 Priority Queue로 불리는 것인지 궁금하실 수 있습니다.
왜냐하면 우리가 Binary Heap를 통해서 구현할 Priority Queue는 Queue처럼 LIFO(Last in First Out)의 형태를 따르기 때문입니다.
즉, Insert연산이 큐의 Enqueue연산과 비슷하고 DeleteMin은 큐의 Dequeue와 비슷합니다. (왜 그렇게 되는지는 밑에서 알아보겠습니다.)
물론 원소를 넣고 빼는 과정에서 우선순위큐가 정렬된 상태를 이루기 때문에 우선순위큐라고 불립니다.
사실 그렇다 보니 정렬방식(오름차순, 내림차순)에 따라서 우선순위가 높은 원소가 최댓값이 될 수도 있고 최솟값이 될수도 있습니다..ㅎㅎ;
2) Applications of Priority Queue
- Data compression : 허프만 코딩 알고리즘
- Shortest path algorithm : 다익스트라 알고리즘
- MST(Minimum Spanning Tree algorithm) : 프림 알고리즘
- Selection problem : Finding kth smallest element
2-1. 허프만 코딩 알고리즘
허프만 코딩 알고리즘은 이전 포스트에도 언급이 되었는데요, 데이터 압축을 위해서 각각의 원소(예, 문자열) 들을 빈도에 따라서 빈도가 큰 문자열은 짧은 비트수를 갖는 표현으로 대응시키는 것을 의미합니다. (대략적인 설명은 위 링크를 참고하세요)
이를 위해서 Huffman coding tree가 필요한데요, 이는 우선순위에 따라서 각각 원소들을 배열하며, left child로 갈 수록 비트 ‘0’을 추가하고, right child로 갈 수록 비트 ‘1’을 추가하는 형식입니다.
이러한 Huffman coding tree를 만들기 위해서 우선순위큐를 이용하고, 그 방식은 다음과 같습니다.
- 각 (문자,빈도)를 가지는 leaf 노드들을 만들고 우선순위큐에 넣는다.
- 이 때 우선순위큐의 key는 빈도가 됩니다.
- Dequeue를 통해 빈도가 낮은 순서대로 뽑히게 정렬합니다.
- 우선순위큐의 원소가 존재할 때 까지 반복
- 두개의 노드를 Dequeue
- 새로운 노드를 만든다
- 위치 : Dequeue한 두 노드를 자식노드로 가짐.
- key : Dequeue한 두 노드들 key의 합
- 새로운 노드를 Enqueue
- 원소가 하나 남은 노드는 root노드로 처리한다.
우선순위큐를 사용하는 이유는 빈도가 낮은 원소를 우선적으로 뽑음으로써 더 많은 조상노드들을 만들기 위함입니다.
(그렇게 되면 더 밑에 깔리므로 더 많은 비트수를 가지게 되겠습니다!)
물론 이 과정 뿐만 아니라, Leaf 노드들의 위치를 파악해서 적절한 비트를 매기고, 다시 복호화하는 과정들도 필요합니다.
2-2. 다익스트라 알고리즘
다익스트라 알고리즘은 Weighted graph에서 쓰이며,
주어진 노드 A와 다른 모든 노드들 간의 최단거리를 찾을 때 쓰입니다.
방식은 다음과 같습니다.
A를 제외한 모든 노드들에 대해 (노드,key)를 우선순위큐에 넣는다!
- 여기서 key는 노드 A를 잇는 edge의 weight(가중치)를 의미합니다.
우선순위큐의 원소가 남지 않을 때 까지 다음을 시행합니다.
Weight가 최소인 노드 B와 그 가중치 Weight(A, B)를 꺼낸다.
우선순위큐에 남아있는 임의의 노드(C)에 대해서 다음을 시행합니다.
인접행렬을 이용해 Weight(B, C)를 계산한다.
- C의 key ( = Weight(A, C) ) 와 Weight(A, B) + Weight(B, C)를 비교한다.
- IF Weight(A,C) > Weight(A, B) + Weight(B, C):
- 우선순위큐에 있는 ( C, Weight(A,C) )를 ( C, Weight(A, B) + Weight(B, C) ) 로 갱신한다.
- Weight(A,C) <- Weight(A, B) + Weight(B, C)
다익스트라 알고리즘을 잘 설명해놓은 예시를 참고하려면 여기를 클릭하세요.
그런데 왜 하필 우선순위큐를 사용할까요?
왜냐하면 가중치가 작은 노드를 먼저 꺼내서 가중치를 갱신하는 일을 적게 하게끔 하기 위함입니다.
생각해보면 A와의 가중치가 가장 작은 노드는 추가적인 갱신 작업 없이 바로 가중치가 확정되겠죠. (왜냐하면 처음부터 바로 우선순위큐에서 Dequeue당하기 때문입니다.)
그런데 이러한 논리가 잘 맞아떨어지려면 가중치가 음수인 노드가 없어야 한다는 가정이 필요합니다.
그래서 알고리즘에 약간의 제한이 있지만 어자피 음수가 있어도 최솟값만큼 더하면 전부 양수가 되기 때문에 큰 문제는 없다고 생각합니다.
…
그 외에 Minimum spanning tree를 구하는 Prim Algorithm이 있는데, 이건 그래프론에서 취급하는 Tree에 대해서 따로 설명을 해야할 것 같아서 때가 되면 나중에 포스트를 하도록 하겠습니다.
3) Binary Heap (이진힙)
3-1. Heap & Binary Heap
Heap은 두 가지 성질을 가지는 트리입니다.
-
heap property : 자식 노드의 값이 부모 노드의 값보다 항상 작거나 같다.
-
h가 트리의 높이라고 한다면, 모든 leaf들은 h나 h-1의 높이를 가집니다.
Heap의 예시 )
그리고 Binary heap은 Binary tree과 비슷하게 heap에 하나의 성질이 더 추가됩니다.
- 자식노드가 2개 이하이다.
그렇기 때문에 Binary Heap은 무조건 complete binary tree 입니다.
3-2. Binary Heap의 장점
이진힙은 항상 배열로 나타낼 수 있습니다.
예를 들어봅시다. 아래의 binary heap을 왼쪽 순서대로 읽으면 이렇게 됩니다.
만약 Complete binary tree가 아니라면 child node가 없기 때문에 array에 빈 원소가 생기게 될 것입니다.
그런데 한 가지 의문이 있는데요, 배열을 통해서도 부모-자식 노드의 관계를 쉽게 구할 수 있을까요? 한번 해봅시다.
0번째 원소의 자식은 1,2번째,
1번째 원소의 자식은 3,4번째
2번째 원소의 자식은 5,6번째
3번째 원소의 자식은 7,8번째…
즉
k번째 원소의 자식은 항상 2k+1, 2k+2번째의 인덱스를 가진다는 것을 귀납적으로 알 수 있습니다.
(반대로 j번째 원소의 부모 인덱스는 (j-1)/2 를 버림한 값이라는 것도 알 수 있습니다.)
결론적으로 Complete binary Tree를 배열로 만들면 인덱스에 대한 접근시간이 짧아질 뿐만 아니라, 트리의 성질들을 모두 활용할 수 있습니다.
4) Implementation
그런데 binary heap을 array로 표현할 때 관례상 0번째 칸을 비워둡니다.
왜냐하면 binary heap이 fully binary tree인지 구분해야할 필요가 있기 때문인데요,
높이가 h인 fully binary tree는 원소개수가 (2^h -1) 이므로 1을 더하면 깔끔하게 2의 거듭제곱 형태가 됩니다.
그렇기 때문에 0번째 칸을 비워둠으로써 2^h-1개의 원소가 heap에 들어와서 완전이진트리가 되면 array의 size가 2의 거듭제곱이 되고, 비트연산을 통해서 파악하기가 훨씬 수월합니다.
4-1. 자식과 부모의 인덱스 얻기
def parent(self,index):
return int(index/2)
def leftChild(self,index):
return 2*index
def rightChild(self,index):
return 2*index + 1
0번째 칸을 비워뒀기 때문에 자식과 부모의 인덱스 관계도 약간 바뀝니다. 헷갈리지마세요!
4-2. Overview
Binary heap의 특성상 첫번째 노드는 확실히 최댓값이지만, 마지막 노드는 최솟값이 아닐수도 있습니다.
어자피 최솟값이 leaf node들 중에 있는건 맞긴 하지만, leaf node의 개수도 n과 비례해서 증가하므로 이진힙으로 최솟값을 구하려는 욕심은 버려야합니다.
즉, 정렬된 값을 들고오기 위해서는 확실한 첫번째 원소(Root Node)를 들고올 수 밖에 없습니다.
하지만, Root Node를 함부러 들고온다면 트리의 구조가 무너지기 때문에 잘 생각해야합니다.
4-3. Init
class MaxHeap:
def __init__(self):
self.size = 0 # 실질적으로 들어있는 노드의 개수
self.heapList = [0] # 1번째 원소부터 시작할거임.
self.bitnum = 0 # 비트연산을 하기위한 멤버변수
생성자는 이렇습니다. 실질적으로 노드들은 heapList 멤버변수에 있습니다. (첫번째 원소는 0이라고 뒀습니다.)
앞서 이진힙이 완전이진트리인지 판별해야할 필요가 있다고 했는데
그 이유는 배열의 동적 크기조정을 위해서입니다.
트리와는 달리 배열은 크기가 정해져있고 이 점을 보완하기 위해서
배열의 크기를 2배씩 resizing하는 dynamic array가 그나마 효율적인 대안이기 때문입니다.
이 resizing을 트리 관점에서 생각하면 트리의 높이가 증가할 때 마다 확장하는 것입니다.
4-4. DeleteMax
역시나 루트노드를 함부러 제거하면 안되기 때문에 우회해서 생각하는게 현명합니다.
최댓값을 제거하는 연산은 몇 가지 step들로 생각할 수 있습니다.
-
첫번째 노드와 마지막 노드의 값을 바꾼다. (17 <-> 3)
-
마지막 노드는 일반적으로 매우 작기 때문에 root에 적합하지 않음
=> heap property를 유지하기 위해 흘려보내야함(percolate-down)
-
percolate-down : 자식노드중에 큰 값을 찾아서 교환하는 작업
- leaf 노드일때는 할 필요가 없으므로 그전까지만 시행
예를 들어서 위와 같은 케이스에서 17을 없애는 과정은 다음과 같습니다.
[0, 17, 15, 6, 1, 4, 4, 3]
[0, 3, 15, 6, 1, 4, 4, 17] # 17 <-> 3
[0, 3, 15, 6, 1, 4, 4, None] # 마지막 원소 삭제
[0, 15, 3, 6, 1, 4, 4, None] # 3 <-> 15
[0, 15, 4, 6, 1, 3, 4, None] # 3 <-> 4
deleteMax를 구현하면 다음과 같습니다.
원리는 간단한데 size를 동적으로 줄이는 작업과, leaf 노드가 있는지 판별하는 작업때문에 코드가 약간 너저분하네요 ㅋㅋ;
def swap(self,idx1,idx2): # 위치바꾸기
self.heapList[idx1],self.heapList[idx2] = self.heapList[idx2], self.heapList[idx1]
def percolatedown(self,index):
"""
1. leftchild 와 rightchild가 전부 존재하지 않을 시 break
2. leftchild 만 존재할 시 걔하고만 크기비교
3. 둘 다 존재할 시 큰값하고 비교
큰값보다 클 시에는 break
"""
while True:
left_index = self.leftChild(index)
right_index = self.rightChild(index)
is_left = self.size >= left_index
are_children = self.size >= right_index
if is_left:
if are_children:
if self.heapList[left_index] > self.heapList[right_index]:
bigger_index = left_index
else:
bigger_index = right_index
if self.heapList[index] > self.heapList[bigger_index]:
break
else:
self.swap(index,bigger_index)
index = bigger_index
else:
if self.heapList[index] > self.heapList[left_index]:
break
else:
self.swap(index,left_index)
index = left_index
else:
break
def deleteMax(self):
"""
size가 2^n 에서 하나 더 줄어들면 동적으로 size를 줄여주는 작업을 병행해야함
ex) size = 4
-> [0 5 4 3 2 None None None]
-> [0 2 4 3 5 None None None] : swap
-> [0 2 4 3] : 타노스
-> [0 4 2 3] : percolatedown
"""
if self.size == 0:
return print("IndexError")
self.swap(1,self.size)
# 동적으로 줄여주는작업
if self.size == (len(self.heapList) // 2):
if self.size != 1:
self.heapList = self.heapList[:(len(self.heapList)//2)]
else:
self.heapList = [0]
return
self.bitnum -= 1
else:
self.heapList[self.size] = None
self.size -= 1
self.percolatedown(1)
4-5 Insert
우선순위큐는 기본적으로 트리구조를 차용했기 때문에 원소를 Leaf 노드로 추가시키는 것이 자연스럽습니다.
즉, 마지막 인덱스에 원소를 추가시키는 것인데요, 이는 Enqueue와 비슷합니다.
역시 heap property를 유지하기 위해서 노드를 위로 올려보내야(percolate-up) 합니다.
percolate-up의 로직은 기본적으로 down과 동일합니다. (부모원소와 비교해서 높으면 swap하기)
def percolateup(self,index):
""" 부모노드랑 값을 비교해서 크기균형이 맞을 때 까지 올려보낼거임."""
while (index > 1):
parent_index = self.parent(index)
if self.heapList[parent_index] > self.heapList[index]:
break
else:
self.swap(parent_index,index)
index = parent_index
def insert(self,value):
"""
size가 2^n -1 에서 하나 더 추가하면 동적으로 size를 늘려주는 작업을 병행해야함.
(heapList의 size는 2^n 일 때 발생하는셈)
"""
if (self.size+1 >> self.bitnum) & 1:
self.heapList += [None for _ in range(len(self.heapList))]
self.bitnum += 1
self.size += 1
self.heapList[self.size] = value
self.percolateup(self.size)
size가 2^n의 꼴이 되야하므로 비트연산을 통해서 사이즈를 비교하였습니다.
예를 들면 이런식으로 시행됩니다.
h = MaxHeap()
array = [1,6,17,15,4,4,3]
for e in array:
h.insert(e)
print(h.heapList)
>>>
[0, 1]
[0, 6, 1, None] # 동적할당
[0, 17, 1, 6]
[0, 17, 15, 6, 1, None, None, None] # 동적할당
[0, 17, 15, 6, 1, 4, None, None]
[0, 17, 15, 6, 1, 4, 4, None]
[0, 17, 15, 6, 1, 4, 4, 3]
4-6 기타
이진힙이 BST나 AVL TREE에 비해서 가지는 장점은 Maximum을 확인하는 연산이 매우 쉽다는 것입니다. 그래서 매우 간단하지만 빼놓을 수가 없습니다.
def getMaximum(self):
if self.size == 0:
return print("IndexError")
return heapList[1]
4-7 Heap Sort
힙 정렬, 많이 들어보셨을겁니다. Merge Sort, Quick Sort와 더불어 정렬 알고리즘의 하한선인 O(nlogn)의 복잡도를 가지는 몇 안되는 정렬 알고리즘입니다.
힙 정렬은 이진힙의 좋은 성질을 이용해서 원소들을 정렬하는 것인데요. 원리는 매우 간단합니다.
- 주어진 배열의 원소를 이진힙에 넣는다.
- 이진힙의 원소를 전부 빼낸다.
끝입니다.
시간복잡도 logn의 작업을 2n번 병행하기때문에 (물론 n이 계속해서 바뀌긴 하지만..) 총 정렬의 시간복잡도가 O(nlogn)이 되는것은 쉽게 추측할 수 있습니다.