[Python] Priority Queue(우선순위 큐) - 완전 이진 트리로 구현하기

 

 

우선순위 큐는 리스트와 완전 이진 트리를 활용하여 구현하는 두 가지 방법이 있다.

예를 들어, 가장 작은 값을 먼저 빼내야 하는 경우를 생각해보면, 다음과 같은 시간 복잡도가 발생한다.

• 리스트를 이용하는 경우
  정렬되지 않은 리스트에서는 삽입이 O(1)이지만 최소값을 찾는 데 O(N)의 시간 복잡도가 발생한다.
  정렬된 리스트를 사용할 경우, 삽입에 O(NlogN)의 시간이 걸리지만 최소값을 찾는 작업은 O(1)로 수행된다.
• 완전 이진 트리를 이용하는 경우
  삽입과 삭제 모두 O(logN)의 시간 복잡도를 가지므로 더 효율적인 방법이다.

 

완전 이진 트리를 활용하려면 어떻게 구현해야 할까?
완전 이진 트리를 효과적으로 구현하려면 힙(Heap) 자료구조를 사용하는 것이 적합하다.

힙은 완전 이진 트리의 성질을 가지며 우선순위 큐를 구현하기에 최적화된 구조다.

---

완전 이진 트리의 주요 특성

• 꼭 node(left child, right child) 형태로 구현하지 않아도 되고, 리스트로 표현할 수 있다.
  • 리스트로 표현할 경우, 인덱스만 알면 부모 노드와 자식 노드의 위치를 쉽게 계산할 수 있다.
    • 예를 들어, 인덱스 i에 대해:
      • 왼쪽 자식의 인덱스는 2*i + 1
      • 오른쪽 자식의 인덱스는 2*i + 2
  • 이러한 특성은 트리가 "완전 이진 트리"일 때 성립한다.

---

힙(Heap)의 종류

1. Min Heap

• 부모 노드의 값이 자식 노드의 값보다 작은 트리 형태의 자료구조다.

2. Max Heap

• 부모 노드의 값이 자식 노드의 값보다 큰 트리 형태의 자료구조다.

---

기타 특성

• 형제 노드 간에는 대소 관계가 정해지지 않는다.
• 루트 노드는 가장 큰 값(Max Heap) 또는 가장 작은 값(Min Heap)을 갖는다.

---

 

1. min heap 구현하기

# min heap 구현하기

import heapq

min_heap = [5,3,9,4,1,2,6]
heapq.heapify(min_heap) # O(N) -> NlogN 아닌가? 라고도 할 수 있지만.. 일단 O(N)로 알고 넘어가기
heapq.heappop(min_heap) # O(logN)
heapq.heappush(min_heap,1) # O(longN)

 

- heapify 함수를 이용하여 min heap 트리 형태 구조를 list 형태로 나타낼 수 있다.

- dequeue는 heappop()으로 나타낼 수 있다. 가장 위에 있는 루트 노드( = 우선 순위가 높음)를 pop하면 마지막에 있던 노드가 루트로 올라오면서 min heap 구조에 맞게 shift down하면서 조정된다.

- enqueue는 heappush()로 나타낼 수 있다. 맨 마지막에 새로운 노드가 추가되면서 shift up을 하면서 min heap 구조에 맞게 조정된다.

- dequeue, enqueue 둘다 트리의 높이(H), 즉 logN(N은 전체 노드의 개수)만큼의 시간복잡도를 가진다.

 

 

2. max heap 구현하기

# max heap 구현하기 1번 방법

import heapq

max_heap = [5,3,9,4,1,2,6]
max_heap = [(-1 * i, i) for i in max_heap]
heapq._heapify_max(max_heap)
value = heapq._heappop_max(max_heap)

- 함수 _heapify_max()와 _heappop_max()이용

- enqueue는 따로 함수가 없다.

# max heap 구현하기 2번 방법

import heapq

max_heap = [5,3,9,4,1,2,6]
max_heap = [-1 * i for i in max_heap]
heapq.heapify(max_heap)
weight = heapq.heappop(max_heap)
value = -1 * weight

- list의 각 값들에 -1을 곱해서 min heap처럼 나타내기

- dequeue할 때, -1을 다시 곱해줘야한다.

# max heap 구현하기 3번 방법

import heapq

max_heap = [5,3,9,4,1,2,6]
max_heap = [(-1 * i, i) for i in max_heap]
heapq.heapify(max_heap)
weight,value = heapq.heappop(max_heap)

- 2번 방법에서 다시 -1을 곱해주는 번거로움을 없애기 위해, 원래 값을 두번째 값으로 넣어서 튜플로 max_heap 리스트 생성

 

 

우선 순위 큐가 단독으로 코딩테스트 문제로 나오진 않지만, 다익스트라 문제에서 우선 순위 큐가 사용된다.

 

 

 

 

Ref. 개발남노씨 - 코딩테스트 [ALL IN ONE]