Priority Queue & Heap

Priority Queue?

• 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조.

구현방법

1. List 이용

• insert time : O(1)
• delete time : O(N)

2. Heap 이용

• insert time : O(logN)
• delete time : O(logN)

Heap

• max heap, min heap 으로 나뉨
• 완전 이진 트리 (왼쪽에서 오른쪽으로 데이터 insert)

Python 라이브러리 사용

import heapq

def heap(res):
	h = []
	result = []

	for value in res:
    	heapq.heappush(h, value)
    for i in range(len(h)):
    	result.append(heap.heappop(h))
    return result

• 파이썬의 기본 heap 은 min heap
• max heap은 - 붙어야 함