[TIL] - 2022-07-18

1. heap

특정한 규칙을 가지는 트리.
최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전 이진 트리

최소 힙 : 부모 노드의 값이 자식 노드의 값보다 항상 작은 힙
최대 힙 : 부모 노드의 값이 자식 노드의 값보다 항상 큰 힙

<출처: https://www.geeksforgeeks.org/heap-data-structure/minheapandmaxheap/>

파이썬 힙 자료구조

파이썬 힙은 우선순위 큐 알고리즘을 제공

함수

• heapq.heapush(heap, item)
  • item을 heap에 추가
• heapq.heappop(heap)
  • heap에서 가장 작은 원소를 pop
• heapq.heapify(x)
  • 리스트 x를 heap으로 변환(O(N)
• heapq.replace(heap, item)
  • 가장 작은 원소를 pop & item 삽입