[python] 우선순위 큐(Priority Queue)와 힙(Heap)

프로그래머스 알고리즘 고득점 KIT - 힙(Heap)

 

1. 우선순위 큐란?

- 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조

- 데이터를 우선순위에 따라 처리하고 싶을 때 사용(예: 가치가 높은 물건부터 꺼내서 확인해야 하는 경우)

- 구현방법: 리스트 혹은 힙(Heap)이용

자료구조	추출되는 데이터
스택(Stack)	가장 나중에 삽입된 데이터
큐(Queue)	가장 먼저 삽입된 데이터
우선순위 큐(Priority Queue)	가장 우선순위가 높은 데이터

 

2. 힙이란?

- 완전 이진 트리의 한 종류 (루트 → 왼쪽노드 → 오른쪽 노드 순으로 채워지며, 항상 부모 <= 자식 규칙을 따르도록 정렬)

- 루트 노드가 제거되면 마지막 요소가 루트 자리로 이동

import heapq

scoville = [1, 2, 3, 9, 10, 12]

############ heap으로 구현 시

         1
       /   \
      2     3
     / \   /
    9  10 12
    
heapq.heapify(scoville)
scoville # [1, 2, 3, 9, 10, 12]
first = heapq.heappop(scoville)  
############
# 1이 제거되면서마지막 요소인 12를 루트 위치로 이동
# 최소 힙에 맞게 다시 정렬

          12
         / \
        2   3
       / \
      9  10

############

       2
      / \
    12   3
    / \
   9   10

############

       2
      / \
     9   3
    / \
  12  10

############

first # 1
scoville # [2, 9, 3, 12, 10]

 

- 언제쓸까? 최솟값 또는 최댓값을 효율적으로 찾고 삭제(루트 노드를 제거)하거나 삽입해야 할 때 사용

- 최소 힙: 루트 노드(부모 노드)가 가장 작은 값을 가진다. → python은 Min-Heapify가 기본, max는 - 붙여 구현

- 최대 힙: 루트 노드(부모 노드) 가 가장 큰 값을 가진다 (값이 큰 데이터가 우선적으로 제거)

- 단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업(O(NlogN))은 정렬과 동일

- 리스트와 힙의 시간복잡도 비교

우선순위 큐 구현 방식	삽입 시간	삭제 시간
리스트	O(1)	O(n)
힙	O(logN)	O(logN)

 

1) heapq.heapify() : 리스트를 최소 힙 구조로 변환, 루트 노드(리스트의 첫번째 요소)가 항상 가장 작은 값을 가진다.

- 최소 힙에서는 숫자 크기 순서대로 정렬되지 않지만, 부모 노드가 최소가 된다.

import heapq

scoville = [10, 2, 3, 12, 1, 9]

heapq.heapify(scoville)
scoville # [1, 2, 3, 12, 10, 9]
heapq.heapify(scoville)
scoville # [1, 2, 3, 12, 10, 9] 부모노드가 이미 최소라 변화 없음

 

2) heapq.heappop() : 최솟값 반환

import heapq

scoville = [10, 2, 3, 12, 1, 9]

heapq.heapify(scoville) # 리스트를 힙으로 변환해줘야만 heappop이 최솟값을 반환
scoville # [1, 2, 3, 12, 10, 9]
min_value = heapq.heappop(scoville)
min_value # 1

 

3) heapq.heappush(): 힙 규칙을 유지하며 값 추가

import heapq

heap = []

heapq.heappush(heap, 5)
heap # [5]
heapq.heappush(heap, 4)
heap # [4,5]
heapq.heappush(heap, 10)
heap # [4,5,10]

heapq.heappop(heap) # 4
heap # [5,10]

 

4) 최댓값에는 -를 붙여서 사용

import heapq

heap = []

heapq.heappush(heap, -5)
heap # [-5]
heapq.heappush(heap, -4)
heap # [-5, -4]
heapq.heappush(heap, -10)
heap # [-10,-4,-5]

[-i for i in heap] # 10,4,5

 

※ [-10,-5,-4]가 아니라 [-10,-4,-5]가 출력된 이유

- 힙은 트리 구조로 동작하며, 숫자를 정렬하는 것이 목표가 아니다

      -5
     /
   -4

#####################

      -5
     /   \
   -4    -10

#####################

      -10
     /   \
   -4    -5

 

3. 완전 이진 트리란?

- 루트 노드부터 시작하여 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 차례대로 삽입되는 트리

 

- 참고자료: 동빈나 자료구조 https://youtu.be/AjFlp951nz0?si=b2e2GAK-18JwldE4