우선순위큐(PriorityQueue)

• 우선순위의 개념을 큐에 도입한 자료구조
  • 데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나간다.
  • 우선순위 큐는 배열, 연결리스트, 힙으로 구현이 가능하다. 이 중에서 힙(heap) 으로 구현하는 것이 가장 효율적이다.

자료구조 heap

• 완전 이진트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
• 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.
• 힙은 일종의 반정렬 상태(느슨한 정렬 상태)를 유지한다.
  - 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도
  • 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진트리
• 힙 트리에서는 중복된 값을 허용한다. (이진트리에서는 허용하지 않음)

힙의 종류

• 최대 힙 (max heap)
  - 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
• 최소 힙 (min heap)
  - 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
  

파이썬 heapq

heapq 모듈은 이진 트리(binary tree) 기반의 최소 힙(min heap) 자료구조를 제공한다.
min heap 을 사용하면 원소들이 항상 정렬된 상태로 추가되고 삭제되며, min heap 에서 가장 작은 값은 언제나 인덱스 0, 즉 이진트리의 루트에 위치한다. 내부적으로 min heap 내의 모든 원소(k) 는 항상 자식 원소들(2k+1, 2k+2) 보다 크기가 작거나 같도록 원소가 추가되고 삭제된다.

heapq 모듈은 파이썬의 일반 리스트를 최소 힙처럼 다룰 수 있도록 도와준다. 따라서 빈 리스트를 생성하고 heapq 모듈의 함수를 호출할 때마다 이 리스트를 인자로 넘겨야한다.

import heapq 

heap = []

# 힙에 원소 추가
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)
heapq.heappush(heap, 3)

# 가장 작은 원소를 삭제
heapq.heappop(heap) 

# 기존 리트스를 힙으로 변환
num = [4, 1, 7, 3, 8, 5]
heapq.heapify(num) 

관련 문제 풀이

[백준] 강의실 배정 (https://www.acmicpc.net/problem/11000)

import heapq

N = int(input())
class_list = [list(map(int, input().split())) for _ in range(N)]
class_list.sort() # 꼭 정렬해야함

room = []
heapq.heappush(room, class_list[0][1])

for idx in range(1,N):
    if class_list[idx][0] < room[0]:
        heapq.heappush(room, class_list[idx][1])
    else: # 수업 끝나고 이어서 하면 됨
        heapq.heappop(room)
        heapq.heappush(room, class_list[idx][1])

print(len(room))

참고자료

• https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html
• https://www.daleseo.com/python-heapq/