Priority Queue(우선순위 큐)의 구현

Priority Queue(우선순위 큐)

Introduction

• 우선순위 큐는 들어간 순서에 상관 없이 우선순위가 높은 데이터가 먼저 나오는 자료구조
• 우선순위 큐를 구현하는 방법
  1. 배열을 기반으로 구현: 데이터를 삽입 및 삭제하는 과정에서 데이터를 한 칸씩 뒤로 밀거나 한 칸씩 당기는 연산을 수반해야 함 + 원소의 삽입 위치를 찾기 위해 배열의 저장된 모든 데이터와 우선순위의 비교를 진행해야 할 수도 있음
  2. 연결 리스트를 기반으로 구현: 원소의 삽입 위치를 찾기 위해 첫 번째 노드에서부터 마지막 노드까지에 저장된 데이터들과 우선순위의 비교를 진행해야 할 수도 있음
  3. 힙을 이용하여 구현
• 우선순위 큐의 logarithmic한 성능을 보장하기 위해 항상 이진 트리의 균형을 맞추어야 함
• 완전 이진 트리(Complete Binary Tree)의 구조를 이용하여 트리의 균형을 맞춤
• 힙을 기반으로 한 우선순위 큐는 트리의 높이에 해당하는 수만큼 비교연산(삽입 및 삭제를 위한)을 진행하게 됨
  • 힙 기반 데이터 저장의 시간 복잡도: O(logN)
  • 힙 기반 데이터 삭제의 시간 복잡도: O(logN)

우선순위 큐 구현에 필요한 기본 연산

• BinaryHeap(): 새로운 Binary Heap을 생성
• insert(item): heap에 새로운 원소 추가
• findMin(): heap에서 가장 작은 값을 가진 원소의 값 반환
• delMin(): heap에서 가장 작은 값을 가진 원소의 값 반환 후 삭제
• isEmpty(): heap의 empty 여부를 boolean 값으로 반환
• size(): heap의 원소 개수 반환
• buildHeap(list): 원소들을 지닌 list로 heap을 새로이 생성

우선순위 큐의 로직

# 클래스와 생성자
class BinaryHeap:
	def __init__(self):
			self.heapList = [0]
			self.currentSize = 0

• 배열의 0번 index는 사용하지 않음
• 따라서 힙에 저장된 노드의 전체 개수와 마지막 노드의 index가 일치

def percUp(self, i):
	# parent 원소가 0보다 큰 index에 위치해 있을 때 까지 반복
	while i // 2 > 0:
		# 추가된 원소가 Parent 원소보다 우선순위가 높을 경우 두 값을 swap
		if self.heapList[i] < self.heapList[i // 2]:
			tmp = self.heapList[i // 2]
			self.heapList[i // 2] = self.heapList[i]
			self.heapList[i] = tmp
		i = i // 2

def insert(self, item):
	self.heapList.append(k)
	self.currentSize = self.currentSize + 1
	self.percUp(self.currentSize)

• 가장 쉽고 효율적인 원소 추가 방법은 list의 가장 끝에 원소를 새로이 추가해주는 것
• 새로이 추가된 원소와 그 Parent의 값을 비교하며, 추가된 원소의 우선순위가 더 높을 경우 두 값을 swap하는 방식을 반복해서 수행
• 우선순위가 높은 신규 원소의 값을 위의 level로 올리는 과정에서 heap의 구조적 특징을 다시 회복

def percDown(self, i):
	# Child 원소가 Heap의 사이즈보다 작거나 같을 때 까지 반복
	while (i * 2) <= self.currentSize:
		# 우선순위가 더 작은 child 노드의 값 선정
		mc = self.minChild(i)
		# child 노드보다 우선순위가 낮을 경우, 두 값을 swap
		if self.heapList[i] > self.heapList[mc]:
			tmp = self.heapList[i]
			self.heapList[i] = self.heapList[mc]
			self.heapList[mc] = tmp
		# 다음 비교를 위해 자식 노드의 index로 변경
		i = mc

def minChild(self, i):
	# Left child node만 있는 경우(완전 이진 트리이므로)
	if i * 2 + 1 > self.currentSize:
		return i * 2

	# 두 개의 child node가 모두 있는 경우
	else:
		if self.heapList[i*2] < self.heapList[i*2+1]:
			return i * 2
		else:
			return i * 2 + 1

def delMin(self):
	retval = self.heapList[1]
	self.heapList[1] = self.heapList[self.currentSize]
	self.currentSize = self.currentSize - 1
	self.heapList.pop() # 이미 루트 자리로 이동하였으므로, 제거
	self.percDown(1)
	return retval

• 루트 노드의 원소가 가장 우선순위가 높은 원소이기 때문에 우선순위가 높은 원소를 찾는 것은 매우 쉬움
• 어려운 부분은 루트 노드를 삭제한 후 다시금 heap의 구조를 정상적으로 회복시키는 것
• 가장 끝에 있는 원소를 루트 노드의 자리로 이동
  • 루트 노드로 이동한 원소와 해당 노드의 자식 노드들의 우선순위를 비교해가며 swap 해가는 방식을 통해 다시 heap의 특성을 갖출 수 있음

def buildHeap(self, alist):
	i = len(alist) // 2
	self.currentSize = len(alist)
	self.heapList = [0] + alist[:]
	while(i > 0):
		self.percDown(i)
		i = i - 1

• heap이 완전 이진 트리로 구성되어 있기 때문에 i는 항상 최하단의 바로 윗 레벨에서 시작하게 됨
• i를 줄여나가며 percDown 연산을 수행하기 때문에 결국 모든 원소의 값이 자신의 우선순위에 맞는 자리를 찾아가게 됨

전체 코드

class BinaryHeap:
    def __init__(self):
        self.heapList = [0]
        self.currentSize = 0
 
    def percUp(self, i):
        while i // 2 > 0:
            if self.heapList[i] < self.heapList[i // 2]:
                tmp = self.heapList[i // 2]
                self.heapList[i // 2] = self.heapList[i]
                self.heapList[i] = tmp
            i = i // 2
 
    def insert(self, k):
        self.heapList.append(k)
        self.currentSize = self.currentSize + 1
        self.percUp(self.currentSize)
 
    def percDown(self, i):
        while i * 2 <= self.currentSize:
            mc = self.minChild(i)
            if self.heapList[i] > self.heapList[mc]:
                tmp = self.heapList[i]
                self.heapList[i] = self.heapList[mc]
                self.heapList[mc] = tmp
            i = mc
 
    def minChild(self, i):
        if i * 2 + 1 > self.currentSize:
            return i * 2
        else:
            if self.heapList[i*2] < self.heapList[i*2+1]:
                return i * 2
            else:
                return i * 2 + 1
 
    def delMin(self):
        retval = self.heapList[1]
        self.heapList[1] = self.heapList[self.currentSize]
        self.currentSize = self.currentSize - 1
        self.heapList.pop()
        self.percDown(1)
        return retval
 
    def findMin(self):
        retval = self.heapList[1]
        return retval
 
    def isEmpty(self):
        if self.currentSize == 0:
            return True
        else:
            return False
 
    def size(self):
        retval = self.currentSize
        return retval
 
    def buildHeap(self, alist):
        i = len(alist) // 2
        self.currentSize = len(alist)
        self.heapList = [0] + alist[:]
        while(i > 0):
            self.percDown(i)
            i = i - 1

[Reference]
Problem Solving with Algorithms and Data Structure
윤성우의 열혈 자료구조