[알고리즘/자료구조] 힙(Heap)

 

📒 힙(heap)

• 완전 이진 트리(Complete Binary Tree)
• 최소 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작은 힙 (루트가 가장 작음)
• 최대 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 힙 (루트가 가장 큼)

https://www.geeksforgeeks.org/heap-data-structure/

 

📒 힙 자료구조 구현

• heapq 모듈 이용
  • heapq.heappush(heap, item): item을 heap에 추가
  • heapq.heappop(heap): heap에서 가장 작은 원소를 pop
    • return 하지 않고 접근만 하려면 인덱스로 접근
  • heapq.heapify(x): 리스트 x를 즉각적으로 heap으로 변환함

 

✏️ heapq 모듈을 이용하여 최소 힙 구현

• heapq 모듈은 기본적으로 최소 힙으로 구현되어 있음

import heapq

heap = []
heapq.heappush(heap, 50)
heapq.heappush(heap, 10)
heapq.heappush(heap, 20)

print(heap)

# 출력 결과: [10, 50, 20]

 

✏️ heapq 모듈 이용하여 최대 힙 구현

• y = -x 변환을 하면 최솟값 정렬이 최댓값 정렬로 바뀜

import heapq

heap_items = [1,3,5,7,9]

max_heap = []
for item in heap_items:
  heapq.heappush(max_heap, (-item, item))

print(max_heap)

# 출력 결과: [(-9, 9), (-7, 7), (-3, 3), (-1, 1), (-5, 5)]

 

---

 

[참고]

[Python] 힙 자료구조 / 힙큐(heapq) / 파이썬에서 heapq 모듈 사용하기

 

자료구조 - 우선순위 큐(Priority Queue)와 힙(heap)