[자료구조] 우선순위 큐

• 우선순위 큐: 우선 순위가 높은 데이터가 먼저 나가는 형태

 

• heap을 이용하여 구현
  • 힙: 우선순위 큐를 위해 고안된 완전이진트리 형태의 자료구조
  • 이진탐색트리와 달리 중복된 값 허용
  • max heap: 부모 키 값이 자식보다 크거나 같은 완전이진트리 (내림차순)
  • min heap: 부모 키 값이 자식보다 작거나 같은 완전이진트리 (오름차순)
• 루트노드가 가방 우선 순위가 높음
• 연산
  1. 값 구하기:
     • 왼쪽 자식 노드 index = 부모노드 index *2
     • 오른쪽 자식 노드 index = 부모노드 index *2 +1
     • 부모 노드 index = 자식노드 index / 2
  2. 삽입 연산
     1. 마지막 노드에 이어서 새로운 노드 추가
     2. 추가된 새로운 노드를 부모노드와 비굫여 교환 & 교환할 필요 없을 때까지 반복
  3. 삭제 연산
     • 루트노드 삭제 (우선순위 높음)
     • 루트노드 자리에 마지막 노드 가져옴
     • 자식노드와 비교하며 교환 (최대 힙인 경우, 더 큰 값과 교환 & 최소 힙인 경우, 더 작은 값과 교환)연산 

 

 

 

• 코드 (python)

1. PriorityQueue() 사용
   • 원소 추가: a.put(값)
   • 원소 삭제: a.get() → 삭제된 원소 리턴, 값이 작은 순서대로 삭제 됨
   • put(값) & get() ⇒ O(log n) 시간 복잡도

from queue import PriorityQueue
a= PriorityQueue()

# 원소추가 ex)3
a.put(3)

# 원소삭제-> 삭제된 원소 리턴, 값이 작은 순서대로 삭제 됨
a.get()

 

 

 

2.  heapq 사용  → 이게 더 효율적 

• 실제로 백준 같은 곳에서 PriorityQueue()를 이용해서 효율성에서 틀린 경우, PriorityQueue()대신  heapq를 사용하게 되면 통과가 될 수 있다. (찾아본 결과 내부적으로 source코드는 비슷한데,  쓰레드 사용 방법이 달라서 그런 것 같다.)
  
  • 값 넣기: heapq.heapqify(리스트) [O(nlogn)], heapq.heappush(힙, 값)
  • 갑 빼기: heapq.heappop(힙) - 젤 작은 것 빼줌
  • 최소값으로 정렬되어 pop 하면 젤 작은 값 먼저 나감 (list를 뽑았을 때는 딱히 정령 안되어 있음)
  • tuple 을 넣을 경우, (a,b) a가 같으면 b 순으로 정렬

import heapq
a=[1,2,3]
heapq.heapify(a) # list를 우선순위큐로 바꾸기

# 우선순위가 낮은 것 삭제, 값 가져오기
b= heapq.heapop(a) # a=[2,3], b=2

# 값 넣기
heapq.heappush(a, 2) # a= [2,2,3]

 

 

 

• 시간 복잡도 비교

구현 방법	삽입	삭제
순서없는 배열	O(1)	O(n)
순서없는 연결 리스트	O(1)	O(n)
정렬된 배열	O(1)	O(1)
정렬된 연결리스트	O(n)	O(1)
힙	O(log2n)	O(log2n)