[Data Structure] Priority Queue

 

오랜만에 자료구조 내용이다. 우선순위 큐를 하기 전에 다양한 자료구조들에 대해 간략하게 짚고 넘어가자

1. Stack
   First In Last Out 방식이다. 가장 먼저 들어간 데이터가 가장 나중에 나온다.
2. Queue
   First In First Out 방식으로 큐와는 반대로 가장 먼저 들어간 데이터가 가장 먼저 나온다.
3. Deque 
   stack 과 queue의 중간 성질을 가진다. 양방향으로 input, output이 가능하다.

 

Priority Queue

Priority Queue(우선순위 큐)는 '가장 우선순위가 높은 원소'를 먼저 나오게 하는 자료구조이다. 이때, 우선순위는 Total Order를 지키는 어떠한 키로도 설정할 수 있다. 가장 기본적으로 가장 작은 값을 출력하는 min priority queue를 많이 사용한다.

 

Total Order

수학적으로 값을 비교하기 위해서는 total order를 만족해야한다. 이를 충족하지 않는 데이터들은 비교를 할 수 없다. 
total order를 만족하지 않는 대표적인 예시가 '가위바위보'이다. 이기는 경우를 더 크다고 정의하면, 가위는 보자기보다 크지만 보자기는 주먹보다 크고 그 주먹은 가위보다 크다. 결국 서로서로 비교할 수 없는 순환관계가 되버린다. 이런 판단 과정을 수학적으로 정리해둔 것이라고 생각하면 된다. 

• Anti-symmetric
  if a <= b and b <= a, then a == b
• Transitivity
  if a <= b and b <= c, then a <= c
• Totality
  for every pair of elements a and b, either a<b or a>b or a==b (셋 중 하나는 무조건 참이어야한다)

읽어보면 너무 간단한 규칙들이다. 어떠한 데이터들을 비교할 때는 total order를 만족하는 경우에만 가능하다. 

 

정렬을 이용한 우선순위 큐

우선 우리는 다양한 우선순위 중 가장 간단한 최솟값을 찾는 min priority queue로 예시를 들 것이다. min priority queue는 꺼낼 때 항상 queue의 값 중 가장 작은 값을 출력한다. 

• 꺼낼 때 가장 작은 값 찾아서 꺼내기
  넣을 때 그냥 배열의 마지막 값에 넣고 꺼낼 때 가장 작은 값을 찾는 방식이다. 
  무작위로 들어간 배열에서 가장 작은 값을 꺼낼 때에는 모든 값을 한번씩 보고 최솟값을 찾는 방법을 사용하면 되기 때문에 ~N 만큼의 시간이 소요된다. 
• 넣을 때 정렬해서 넣기
  꺼낼 때 시간이 많이 걸리니까 그냥 넣을 때부터 예쁘게 넣는 방식을 생각해보자. 추가할 위치를 찾는 것은 이진 탐색을 사용하면 ~logN 만큼 소요된다. 이후 원소들을 한 칸씩 뒤로 옮길 때 ~N 만큼의 시간이 걸리니 삽입하는데에는 ~N의 시간이 소요된다. 하지만 삭제는 첫번째 원소를 제거하면 되기 때문에 ~1만큼의 시간이 걸린다.

	Unordered list ( 꺼낼 때 작은 값 찾기)	Ordered List ( 넣을 때 정렬해서 넣기)
insert	~1	~N
delete	~N	~1

결국 한 원소를 삽입/삭제를 하면 ~N의 시간만큼 걸리는데 N개의 데이터를 이용해 삽입 삭제를 한번씩 거치면 ~N^2이 된다. 더 시간복잡도를 줄일 수 있는 방법이 없을까?

 

Heap을 이용한 우선순위 큐의 구현

많은 언어들이 우선순위 큐를 Binary heap을 사용해 구현하고 있다. 

Complete Binary Tree

binary tree : 모든 노드의 자식이 최대 2개인 tree
Complete tree : 모든 level이 빈 곳 없이 가득 차 있으며, 가장 아래 level은 왼쪽 부터 빈 곳없이 차례로 채워진 tree

노드 수가 k 개인 완전이진트리는 무조건 하나의 모양밖에 나올 수 없다. 

트리를 사용하는 이유는 tree는 트리 깊이가 logN에 비례하기 때문에 많은 연산의 시간을 ~logN에 가능하게 해준다. 또한, complete binary tree를 사용하는 이유는 배열에 값을 넣었을 때 부모-자식 간의 연산이 매우 간단해진다. 

• parent = child *2 or child * 2 +1
• child : parent // 2

위 연산이 가능하게 하려면 첫번째 root 노드의 값을 index 1에 저장해야한다. 

i	0	1	2	3	4	5	6	7	8
a[i]		2	4	7	5	9	8	10	8

위 배열은 아래 tree를 나타낸다. 

min heap이 되려면 부모의 node 값이 자식 node의 값보다 작아야한다. 

 

 

priority queue - insert

min heap을 유지하기 위한 조건을 한번 더 정리해보자

• 부모 노드의 값이 자식 노드의 값보다 작아야한다.(heap order를 유지해야한다.)
• complete binary tree 형태를 유지해야한다.
• (추가 조건) logN 시간에 연산을 끝내보자

insert 하는 방식은 일단 먼저 complete binary tree 형태를 유지한 다음, 해당하는 자리로 거슬러 올라간다. 

위의 예제에 3을 넣어보자

일단 heap order를 상관하지 말고 값을 넣는다. 그 다음 heap order를 맞추기 위해 부모와 비교하면서 값을 바꾼다. 

마치 수영하면서 위로 올라가는 것과 비슷하다 하여 swim up이라고 부른다. 이때, 거슬러 올라갈 수 있는 최대 높이는 tree의 높이와 비례하기 때문에 ~logN의 시간이 소요된다.

class MaxHeap:
	def __init__(self):
    	self.pq = [''] # empty key
    
    def insert(self, key):
    	self.pq.append(key)
        idx = len(self.pq) -1
        
        while idx > 1 and self.pq[idx//2] > key : # 부모가 더 값이 크다면 
        	self.pq[idx], self.pq[idx//2] = self.pq[idx//2], self.pq[idx]
            idx = idx//2

 

priority queue - delete

heap을 구현했으면 삭제해야하는 값은 root이다. 하지만, root를 삭제하면 tree 구조가 깨지기 때문에 root를 삭제한 뒤 맨 마지막 값을 root로 가져온다. 그 다음 total order를 자식들과 비교하며 heap을 유지한다. 

위 예제에서 삭제를 해보겠다. 

삭제하고 맨 마지막에 있는 5를 맨 위로 올렸다. 이렇게만 하면 heap의 order가 맞지 않으니 자식들과 비교하며 값을 교체해준다. 

이렇게 완료가 된다. 이 방식도 삭제한 뒤 tree의 깊이만큼 값을 찾아다니면서 수정하면 되기 때문에 ~logN 이 소요된다. 이 방식은 마치 root의 값이 가라앉는 것과 유사하다는 의미로 sink라고 한다. 

def defMin(self):
	self.pq[1], self.pq[len(self.pq)-1] =  self.pq[len(self.pq)-1], self.pq[1]
    max = self.pq.pop()
    idx = 1
    while 2 * idx <= len(self.pq)-1:
    	idxChild = 2 * idx
        
        if idxChild < len(self.pq) - 1 and self.pq[idxChild] > self.pq[idxChild+1]:
        	idxChild = idxChild + 1
        if self.pq[idx] <= self.pq[idxChild]:
        	break
        self.pq[idx], self.pq[idxChild] = self.pq[idxChild], self.pq[idx]
        idx = idxChild
    return max

 

시간복잡도 정리

	insert()	delMin()
Binary Heap	~log2(N)	~log2(N)