[자료구조]heap 익히기

heap 자료구조

• binary tree 를 가정
• 최소힙 또는 최대힙이 있고, 아래 예시는 최소힙을 가정하고 든 예시
• 시간복잡도가 log(n) 으로 우선순위 큐와 같은 자료구조보다 효율적인 알고리즘 구현 가능

Reference

• 고려대학교 뇌영상분석연구실 교육자료 참고.

minimum heap 자료구조에 5 삽입(insert) 시 root node로 도달하는 과정

import heapq as hp
x=[3,2,1,4,5]
hp.heapify(x) # heap으로 만듦
print(x)

>> [1, 2, 3, 4, 5]

hp.heappush(x,3) # item 삽입
print(x)

>> [1, 2, 3, 4, 5, 3] # binary tree의 마지막 노드에 추가됨

hp.heappop(x) # 최솟값 삭제 delete_min
print(x)

>> [2, 3, 3, 4, 5] 

hp.heappushpop(x,1) # item 삽입 후 delete_min 수행
print(x)

>> [2, 3, 3, 4, 5]  # 1이 최소였기에 그낭 튀어나왔음

hp.heapreplace(x,1) #delete 먼저 한다음 item 삽입
print(x) 

>> [1, 3, 3, 4, 5] # 1로 대체되었다 (replace)