[PYTHON] heap 자료구조 - heapq 라이브러리

Heap

: 우선순위 큐(priority queue)를 구현하거나 효율적인 탐색/정렬 알고리즘에서 사용되는 트리 기반의 자료구조

 

Heap 특징

완전 이진 트리(Complete Binary Tree): 모든 레벨이 꽉 차 있고 마지막 레벨의 노드는 왼쪽부터 채워진다

 

Heap 속성

최대 힙(Max-Heap) : 부모 노드의 값이 자식 노드의 값보다 크거나 같다
최소 힙(Min-Heap) : 부모 노드의 값이 자식 노드의 값보다 작거나 같다

 

파이썬 heapq 모듈

: 파이썬에서는 힙 자료구조를 효율적으로 다룰 수 있도록 최소 힙(Min-Heap) 기반의 heapq 모듈을 제공한다

 

heapq 모듈 주요 함수

• heapq.heappush(heap, item) : heap에 item을 추가
• heapq.heappop(heap) : heap에서 가장 작은 값을 제거하고 반환
• heapq.heapify(list) : list를 heap으로 변환

heapq.heappush(heap, item)

import heapq

heap_list = []

heapq.heappush(heap_list,6)
heapq.heappush(heap_list,9)
heapq.heappush(heap_list,3)

print(heap_list) #[3,6,9]

 

heapq.heappop(heap)

heapq.heappop(heap_list) #3

print(heap_list) #[6,9]

 

heapq.heapify(list) 

test_list = [2,1,3,5,4]

heapq.heapify(test_list)

print(test_list) #[1, 2, 3, 5, 4]

 

최대 힙 구현 예시 -  음수로 변환

import heapq

nums = [5, 1, 3, 8, 2]
max_heap = []

# 음수로 변환하여 최대 힙 구현
for num in nums:
    heapq.heappush(max_heap, (-num,num))

print(max_heap) #[(-8, 8), (-5, 5), (-3, 3), (-1, 1), (-2, 2)]

 

heap 활용 문제

https://1ooflower.tistory.com/106

[프로그래머스] 더 맵게 - python