[Python] Heap

Heap

---

• 최댓값 및 최소값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리 기반의 자료구조

속성

• 최대힙 : 부모노드의 키값이 자식노드의 키값보다 항상 큼
• 최소힙: 부모노드의 치값이 자식노드의 키값보다 항상 작음
• 우선순위가 가장 높은/낮은 노드가 항상 루트로

시간 복잡도

$O(log n)$

Python의 Heap

---

모듈 임포트

import heapq

• 이진트리기반 최소힙 제공

  → 최소값이 항상 인덱스 0

• 내부적으로 모든 원소는 항상 자식 원소보다 작거나 같도록 추가/삭제

최소힙 생성

heap = []

→ 일반 리스트를 마치 최소힙처럼 다룰 수 있게 제공

원소 추가

heapq.heappush(heap, 1)
heapq.heappush(heap, 5)
heapq.heappush(heap, 4)

print(heap)
#[1, 4, 5]

원소 삭제

: heap[0] 삭제 후 그 값 리턴

heapq.heappop(heap)

print(heap)
#[4,5]

기존 리스트를 힙으로

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

print(heap)
#[1, 3, 4, 5, 7]

최대 힙 구현

: (우선순위, 값) 구조의 튜플을 힙에 추가

∵ 힙에 튜플 추가,삭제 시 튜플의 첫번째 원소 기준으로 최소 힙 구성

import heapq

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

for num in nums:
	heapq.heappush(heap, (-num, num))