[자료구조] 우선순위 큐(Priority Que, Heap)

우선순위 큐

큐는 먼저 들어오는 데이터가 먼저 나가는 FIFO 형식의 자료구조이나,

우선순위 큐는 먼저 들어오는 데이터가 아닌, 우선순위가 높은 데이터가 먼저 나간다.

또한, 내부적으로 이진 트리(Binary Tree) 형태의 힙(Heap)이라는 형태로 돌아가게 된다

 

그림을 보면 우선순위 큐를 이진 트리가 있고, 가장 최상단의 root node가 모든 노드를 통틀어 가장 큰 값을 가지고 있다는 것을 알 수 있다.

이와 같이 루트 노드에 큰 값이 들어가있으면 max-heap으로, 루트 노드에 가장 작은 값이 들어가 있으면 min-heap이라 한다

각 트리의 노드에 번호를 붙이고, 이 번호를 배열의 인덱스로 생각하면 효과적으로 힙을 구현할 수 있다

 

삽입/삭제를 한 번 할때 시간 복잡도는 O(logN)을 가지게 된다 (정확히는 밑이 2인 logN이나, 간단하게 O(logN)으로 표기한다)

 

// C++
priority_queue<int> pq;
pq.push(456);
pq.push(123);
pq.push(789);
printf("size: %d\n", pq.size());
while (!pq.empty()){
	printf("%d\n", pq.top());
    pq.pop();
}

C++은 max-heap을 지원한다

# python
import heapq

pq = []
heapq.heappush(pq, 6)
heapq.heappush(pq, 12)
heapq.heappush(pq, 0)
heapq.heappush(pq, -5)
heapq.heappush(pq, 8)
print(pq)
while pq:
	print(pq[0]) # 최상단 노드를 출력한다
	heapq.heappop(pq) # 최상단 노드를 뺀다

파이썬은 min-heap을 지원하여, 가장 작은 값이 맨 앞에 오게 된다