[Data Structure] 우선순위 큐(Priority Queue) & 힙(Heap)

우선순위 큐(Priority Queue)

우선순위 큐(Priority Queue)는 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다.

우선순위 큐의 요소는 모두 우선순위를 가지고 있으며, 우선순위가 같은 경우에는 큐의 순서에 따라 처리한다.

 

우선순위 큐는 여러 방식으로 구현할 수 있지만 힙(heap)이 가장 효율을 보이기 때문에 일반적으로 힙을 이용하여 구현한다.

방식	시간 복잡도
배열	O(N)
연결 리스트	O(N)
힙	O(logN)

 

힙(heap)

힙의 특징

• 완전이진트리 형태로 이루어져 있다.
• 부모노드는 자식노드 사이에 대소관계를 가지고 있다.
• 중복된 키를 허용한다.

 

힙의 종류

• 최대 힙(max heap): 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 힙
• 최소 힙(min heap): 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 힙

 

힙 구현

최대 힙(max heap)

class MaxHeap(object):
	
    def __init__(self):
    	self.queue = []
       
    def insert(self, n):
    	self.queue.append(n)
        last_index = len(self.queue) - 1
        while 0 <= last_index:
        	parent_index = self.parent(last_index)
            if 0 <= parent_index and self.queue[parent_index] < self.queue[last_index]:
            	self.swap(last_index, parent_index)
                last_index = parent_index
            else:
            	break
    
    def delete(self):
    	last_index = len(self.queue) - 1
        if last_index < 0:
        	return -1
        self.swap(0, last_index)
        maxv = self.queue.pop()
        self.maxHeapify(0)
        print(maxv)
        return maxv
    
    def maxHeapify(self, i):
    	left_index = self.leftchild(i)
        right_index = self.rightchild(i)
        max_index = i
        
        if left_index <= len(self.queue) - 1 and self.queue[max_index] < self.queue[left_index]:
        	max_index = left_index
        if right_index <= len(self.queue) - 1 and self.queue[max_index] < self.queue[right_index]:
        	max_index = right_index
        
        if max_index != i:
        	self.swap(i, max_index)
            self.maxHeapify(max_index)
    
    def swap(self, i, parent_index):
    	self.queue[i], self.queue[parent_index] = self.queue[parent_index], self.queue[i]
    
    def parent(self, index):
    	return (index - 1) // 2
    
    def leftchild(self, index):
    	return index * 2 + 1
    
    def rightchild(self, index):
    	return index * 2 + 2
    
    def printHeap(self):
    	print(self.queue)

코드 출처: https://daimhada.tistory.com/108

 

파이썬은 heapq 내장 라이브러리를 제공하여 손쉽게 heap을 사용할 수 있다.

import heapq

heap = []
heapq.heappush(heap, 50)
heapq.heappush(heap, 10)
heapq.heappush(heap, 20)

print(heap) # [10, 50, 20]

• heapq.heappush(heap, object): heap에 object를 추가한다.
• heapq.heappop(heap): heap에서 가장 작은 원소를 pop한다.
• heapq.heapify(list): list를 heap으로 변환시킨다.

heapq 모듈은 최소 힙으로 구현되어 있다. 따라서 최대 힙을 구현하기 위해서는 부호를 활용하는 등의 트릭을 써야 한다.