[알고리즘2] Priority Queue

복습하기 위해 학부 수업 내용을 필기한 내용입니다.
이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다.
그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다.

▶Contents

• Binary Heap을 사용한 PQ의 구현
• Priority Queue 사용 애플리케이션 공통적인 특성
• Slider Puzzle and A* Search with PQ

 

▶Priority Queue

insert()

1. complete binary tree 형태를 유지한다.

2. heap order를 유지한다.

3. ~logN 시간에 새 원소를 추가한다.

 

insert(k)하는 새 값을 k라고 할 때, k를 tree 가장 마지막에(배열 끝에) 추가한다.

k를 부모 노드와 비교해 heap-order(부모 >= 자식) 어긴다면 swap 하는 것을 반복한다. (swim up)

(즉, heap-order 만족할 때까지 부모 노드 따라 계속 올라간다.)

 

index 0은 비워두고 1부터 담는다. -> 부모-자식 접근 식이 더 간단하다.

index 1부터 담기

Node i의 부모 : i // 2,     왼쪽 자식 : i * 2,     오른쪽 자식 : i * 2 + 1

index 0부터 담기

Node i의 부모 : (i - 1) // 2,     왼쪽 자식 : i * 2 + 1,     오른쪽 자식 : i * 2 + 2

class MaxHeap:
	def __init__(self): # Constructor
		self.pq = [''] # Empty key at pq[0]


	def insert(self, key):
		self.pq.append(key) # 새 원소 key를 배열 맨 끝에 추가
		idx = len(self.pq)-1 # idx = 새 원소가 추가된 index
		while idx>1 and self.pq[idx//2] < key: # 부모≥자식 조건 만족할 때까지 반복
			self.pq[idx], self.pq[idx//2] = self.pq[idx//2], self.pq[idx] # key와 부모 swap
			idx = idx//2 # key의 index를 부모가 있던 위치로 변경

Q. insert() 비용은 ~logN으로 제한되는가?

     A. ~lonN으로 제한된다. 왜냐하면 트리의 최대 깊이는 log2 N이기 때문이다.

         가장 마지막 노드에 추가되어서 루트까지 올라간다 하더라도 log2 N만큼만 수행하기 때문이다.

 

 

delMax()

1. complete binary tree 형태를 유지한다.

2. heap order를 유지한다.

3. ~logN 시간에 max를 삭제한다.

 

root 값을 tree 가장 마지막 값 k와 swap 하며 배열에서 삭제한다.

k를 자식 노드 중 큰 쪽과 비교해 heap-order (부모 >= 자식) 어긴다면 swap 하는 것을 반복한다. (sink)

(즉, heap-order를 만족할 때까지 자식 노드 중 큰 쪽을 따라 계속 내려간다.

 

Q. delMax()할 때 root 삭제한 후, 자식 중 더 큰 쪽을 swim up 시키면 안 되는가?

     A. 안된다. 큰 자식을 계속 올리다 보면,

         어떤 경우에는 complete binary tree 형태를 유지할 수 없게 된다.

def delMax(self): 
	# root(max)와 마지막 원소 k swap
	self.pq[1], self.pq[len(self.pq)-1] = self.pq[len(self.pq)-1], self.pq[1]
	max = self.pq.pop() # 마지막에 있는 max 값 제거
	idx = 1 # 마지막 원소 k가 있는 root에서 sink 시작
	while 2*idx <= len(self.pq)-1: # 아래에 자식이 있다면 계속 sink 시도
		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 # heap order 만족하면 sink 중단
		# k와 더 큰 자식 swap함으로써 sink
		self.pq[idx], self.pq[idxChild] = self.pq[idxChild], self.pq[idx]
		idx = idxChild # k의 index를 자식이 있던 위치로 변경
	return max

 

Heap 정리 : heap order 따라 원소를 배치하는 complete binary tree이다.

PQ의 효율적인 구현 방법이다.

(max) heap order : 부모 key >= 자식 key

     따라서 어떤 노드라도 그 아래로 뻗어 나간 모든 노드 중 max, Delete(max 찾기)를 쉽게 한다.

complet binary tree

     실제 트리를 만들지 않고, 배열을 사용해 편리하게 indexing이 가능하다.

     트리 깊이 ~logN으로 제한해서 insert, delete 비용 또한 ~logN으로 제한된다.

구현방식	insert() 비용	delMin() 비용
Unordered list	~1	~N
Ordered array	~N	~1
Binary Heap	~log2 N	~log2 N
d-ary Heap	~logd N	~d * logd N
불가능	~1	~1