힙은 우선순위 큐를 위해 만들어진 자료구조다.
1. 우선순위 큐 (Priority Queue)
우선순위 큐란?
- 큐 : FIFO 형식의 자료구조
- 우선순위 큐는 큐에 우선순위라는 개념을 접목시킨 자료구조이다.
- 따라서, 우선순위 큐는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다.
2. 힙 (Heap)
힙이란?
- 우선순위 큐를 위해 고안된 완전이진트리 형태의 자료구조
- 여러 값 중, 최대값과 최소값을 빠르게 찾아내도록 만들어진 자료구조
- 반정렬 상태를 유지
ex. 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큼 / 작음 - 이진탐색트리(BST)와 달리 중복된 값이 허용된다.
3. 힙의 종류
3.1. 최대 힙 (max heap)
- 부모 노드의 키값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
- key(부모 노드) >= key(자식 노드)
3.2. 최소 힙 (min heap)
- 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
- key(부모 노드) <= key(자식 노드)
4. 힙의 데이터 저장/삭제 개념
4.1. 최소 힙에 저장할 때
A) 들어올 새 노드를 우선순위가 가장 낮다는 가정을 하고 맨 끝 위치에 저장
B) 부모 노드와 우선 순위를 비교해서 위치가 바뀌어야 하면 바꾼다.
C) 올바르게 위치할 때까지 B 반복
4.2. 최소 힙에서 삭제할 때
- 우선순위 큐의 pop == 가장 우선순위가 높은 데이터를 빼낸다
A) 루트 노드를 반환(삭제)하고 마지막 노드(n)를 루트 노드 자리에 옮긴다.
B) n의 왼쪽, 오른쪽 자식노드 중 더 우선순위가 높은 것과 비료를 진행한다.
C) 최소 힙의 구조를 유지할 때까지 B 반복
위의 과정과 같이 힙의 구조를 유지하는 과정을 heapify라고 한다.
5. 파이썬에서의 우선순위 큐
5.1. PriorityQueue
from queue import PriorityQueue
q = PriorityQueue()
q1 = PriorityQueue(maxsize=10) # maxsize를 활용하면 크기 제한 가능put
q.put(3) # 원소를 넣는 과정
q.put(4)
q.put(1)
q1.put((1, 'apple')) # (우선순위, 값)의 형태로 저장할 수도 있음get
# 원소 삭제 및 반환
q.get() # 1
q1.get()[1] # (우선순위, 값)의 형태에서 값 반환5.2. Heapq
- 최소 힙 구조
- 모든 k에 대해
heap[k] <= heap[2*k+1]또는heap[k] <= heap[2*k+2]만족 - 가장 작은 요소가
heap[0]에 위치 - 힙을 만들기 위해서는, 초기화된 리스트
[]를 사용하거나,heapify를 통해 값이 들어있는 리스트를 힙으로 변환 가능
import heapq
hq = []push
- 힙의 형태를 유지하면서 item을 push
heapq.heappush(hq, 4)
heapq.heappush(hq, 1)
heapq.heappush(hq, 3)
heapq.heappush(hq, 7)pop
- 힙의 형태를 유지하면서 가장 작은 항목을 pop(반환)
- 비어있으면 IndexError 발생
- 반환하지 않고 접근하고 싶다면,
heap[0]활용
heapq.heappop(hq) # 1heapify
- 리스트
x를 선형 시간으로 제자리에서 heap으로 변환
x = [4, 3, 1, 2, 5, 6]
print(x) # [4, 3, 1, 2, 5, 6]
heapq.heapify(x)
print(x) # [1, 2, 4, 3, 5, 6]6. 참고 자료
https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html
https://chanhuiseok.github.io/posts/ds-4/
https://velog.io/@mein-figur/Python%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84-%ED%81%90-heapq
chick! chick!