우선순위 큐

 

우선순위 큐(Priority Queue)

우선순위 큐는 우선순위에 따라서 데이터를 추출하는 자료구조

컴퓨터 운영체체, 온라인 게임 매칭 등에 활용 된다.

우선순위 큐는 일반적으로 힙(heap)을 이용해 구현

지료구조	추출되는 데이터
스택(stack)	가장 나중에 삽입된 데이터
큐(queue)	가장 먼저 삽입된 데이터
우선순위 큐(priority queue)	가장 우선순위가 높은 데이터

 

데이터의 개수가 N개 일때, 구현 방식에 따라 시간 복잡도

우선순위 큐 구현 방식	삽입시간	삭제시간
리스트 자료형	O(1)	O(1)
힙(Heap)	O(logN)	O(logN)

 

일반적인 형태의 큐는 선형적 구조가지며, 우선순위 큐는 이진트리의 구조를 사용하는 것이 일반적이다.

 

 

힙(Heap)

원소들 중에서 최댓값 혹은 최솟값을 빠르게 찾아내는 자료구조

완전 이진트리 자료구조를 따른다.

원소의 삽입과 삭제를 위해 O(logN)의 수행 기간을 요구한다.

단순한 N개의 데이터를 힙에 넣고 빼는 작업은 정렬과 동일하다.(시간 복잡도는 O(NlogN))

 

최대 힙(MAX Heap)

값이 큰 원소부터 추출한다.

부모노드가 자식 노드보다 값이 큰 완전 이진 트리를 의미한다.

루트 노드는 전체 트리에서 가장 큰 값을 가진다.

 

최소 힙(Min Heap)

값이 작은 원소부터 추출한다.

부모 노드의 키 값이 자식 노드의 키 값보다 항상 작다.

루트 노드가 가장 작으며, 값이 작은 데이터가 우선순위를 가진다.

 

최소 힙 구성 함수(Heapify)

(상향식)부모로 거슬러 올라가며, 부모보다 작신이 더 작은 경우에 위치를 교체한다.

 

- 새로운 원소가 삽입 되었을 때

O(logN)의 시간 복잡도로 힙 성질을 유지하도록 할 수 있다.

(상향식)부모로 거슬러 올라가며, 부모보다 작신이 더 작은 경우에 위치를 교체한다.

 

- 새로운 원소가 삭제 되었을 때

O(logN)의 시간 복잡도로 힙 성질을 유지하도록 할 수 있다.

원소를 제거할 때는 가장 마지막 노드가 루트 노드의 위치에 오도록 한다.

 

 

heapq 라이브러리

heap = [ ] 힙의 빈 리스트

원소의 삽입 : heappush() 메서드

원소의 추출 : heappop() 매서드

 

heappush() 메서드를 이용해 하나씩 원소를 삽입하지 않을 수 있다.

heapify()  메서드는 새로운 리스트를 반환하지 않고, 리스트 내부를 직접 수정한다.