우선순위 큐

우선순위 큐는 우선순위를 가지는 데이터들을 저장하는 큐를 의미한다. 데이터를 우선순위에 따라 처리하고 싶을 때 사용하는 자료구조이다.

1. 일반 큐 VS 우선순위

• 일반큐 : 선형적인 형태를 가지고 있다.
• 우선순위 큐 : 트리 구조로 본다.

2. 구현 방법

⭐ 단순히 리스트를 이용해서 구현할 수 있다.
⭐ 힙(heap)을 이용하여 구현할 수 있다.

⏩ 시간복잡도

(1) Min Heap(최소 힙)

최소 힙은 부모 노드가 자식 노드보다 값이 작은 완전 이진트리를 의미한다.

(2) Max Heap(최대 힙)

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

💯 우선순위 큐는 추상 자료형(ADT) 즉 순수하게 기능이 무엇인지를 나열한 것을 의미하고, Heap은 이러한 기능을 구현하기위한 도구라고 생각하자.

3. 힙 주요동작

(1) insert

• 삽입할 원소는 완전 이진트리를 유지하며 순차적으로 삽입된다.

(2) delete

• 루트 노드를 삭제하고 가장 마지막 원소를 루트 노드의 위치로 옯긴 뒤 정렬한다.
  

4. Heap라이브러리 사용

(1) 기존리스트를 힙으로 변환

from heapq import heapify

heap = [4, 1, 7, 3, 8, 5]
heapify(heap)
print(heap)

#=====================
[1, 3, 5, 4, 8, 7]

(2) 최소 힙

from heapq import heappop, heappush

h = []
heappush(h,value)
heappop(h) 

(3) 최대 힙

from heapq import heappop, heappush

h = []
heappush(h,-value)
-heappop(h)