우선순위 큐와 힙

힙은 완전 이진 트리 자료구조의 일종이다.
- 완전 이진트리란 루트 노드부터 시작하여 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 차례대로 삽입되는 트리를 의미한다.
항상 루트노드를 제거한다.
최소 힙(min heap)
- 루트 노드가 가장 작은 값을 가진다(부모가 자식보다 작아야)
- 따라서 값이 작은 데이터가 우선적으로 제거된다
최대 힙(max heap)
- 루트 노드가 가장 큰 값을 가진다
- 따라서 값이 큰 데이터가 우선적으로 제거된다

최소 힙 구성 함수: Min-Heapify()

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

힙을 이용해서 정렬하면 그게 힙정렬 O(nlogn)

cf. quick merge 정렬도 O(nlogn)

💻우선순위 큐 라이브러리를 활용한 힙 정렬 구현

import heapq

def heapsort(iterable):
    h = []
    result = []
    # 모든 원소를 차례대로 힙에 삽입
    for value in iterable:
        heapq.heappush(h, value)
    # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for i in range(len(h)):
        result.append(heapq.heappop(h))
    return result

n = int(input())
arr = []
for i in range(n):
    arr.append(int(input()))
res = heapsort(arr)
for i in range(n):
    print(res[i])

파이썬의 경우 기본적으로 힙 자료구조가 최소힙으로 동작

최대힙으로 쓰고 싶으면 데이터 넣을 때 꺼낼 때 - 붙여서

[참고] Youtube, 자료구조: 우선순위 큐(Priority Queue)와 힙(Heap) 10분 핵심 요약

과정

# 모듈 임포트
import heapq
# 최소 힙 생성
'''
heapq 모듈은 파이썬의 리스트를 최소힙처럼 다룰 수 있게 도와준다. 자바의 PriorityQueue 클래스처럼 별개의 자료구조가 아닌 점에 유의.
그렇기 때문에 그냥 빈 리스트를 생성한 다음 heapq 모듈 함수를 호출할 때마다 만든 리스트를 인자로 넘겨야 한다. 즉, 파이썬에서는 heapq 모듈을 통해서 원소를 추가하거나 삭제한 리스트가 그냥 최소힙이 된다.
'''
heap = []
# 힙에 원소 추가
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)
heapq.heappush(heap, 3)
print(heap)
[1, 3, 7, 4]

# 힙에서 원소 삭제
print(heapq.heappop(heap))
print(heap)
1
[3, 4, 7]
'''
가장 작았던 1이 삭제, 리턴되었고 그 다음 작은 3이 인덱스0으로 올라옴.
'''
print(heapq.heappop(heap))
print(heap)
3
[4, 7]
'''
가장 작은 3이 삭제, 리턴 되었고 그 다음 작은 4가 인덱스 0으로 올라옴.
'''

# 최소값 삭제하지 않고 얻기
print(heap[0])
4

기존 리스트를 힙으로 변환

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

[응용] 최대 힙

heapq 모듈은 최소힙 기능만을 동작. 최대힙을 쓰고 싶으면 요령이 필요. 힙에 넣을 때 튜플 형식으로 넣어서 튜플의 0번째에 있는 값을 기준으로 최소힙이 구성되는 원리를 이용.

따라서 최대힙을 만들려면 각 값에 대한 우선순위를 구한 후 (우선순위, 값) 구조의 튜플을 힙에 추가하거나 삭제하면 됨. 그리고 힙에서 값을 읽어올 때는 각 튜플에서 1번째에 있는 값을 가져오면 됨.

import heapq

nums = [4, 1, 7, 3, 8, 5]
heap = []

for num in nums:
  heapq.heappush(heap, (-num, num))  # (우선 순위, 값)

while heap:
  print(heapq.heappop(heap)[1])  # index 1