힙
힙은 특정한 규칙을 가지는 트리로, 최대값과 최소값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한다.
힙은 최소 힙, 최대 힙 두 종류가 존재한다.
최소 힙은 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙이고,
최대 힙은 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙이다.
이때 자식 노드끼리의 대소관계는 신경쓰지 않는다.
파이썬에는 heapq 내부 모듈이 존재해, 간단하게 힙 자료구조를 만들 수 있다.
heapq는 기본적으로 최소 힙으로 구현되어 있다.
모든 k에 대해 heap[k] <= heap[2k+1]과 heap[k] <= heap[2k+2]인 배열을 사용한다.
heapq 함수
heapq.heappush(heap, item)힙 불변성을 유지하면서, item을 heap에 푸시한다.
heapq.heappop(heap)힙 불변성을 유지하면서, heap에서 가장 작은 항목을 팝하고 반환한다.
힙이 비어있으면 IndexError가 발생한다.
팝 하지 않고 가장 작은 항목에 접근하려면, heap[0]을 사용하면 된다.
heapq.heappushpop(heap, item)힙에 item을 푸시한 다음, heap에서 가장 작은 항목을 팝하고 반환한다.
heappush()한 다음 heappop()을 별도로 호출하는 것보다 효율적이다.
heapq.heapify(list)리스트를 힙으로 변환한다. O(N)의 시간 복잡도를 가짐.
heapq.heappreplace(heap, item)heap에서 가장 작은 항목을 팝하고 반환하며, 새로운 item을 푸시한다.
힙 크기는 변경되지 않는다.
힙이 비어있다면 IndexError가 발생한다.
heappop()한 다음 heappush()하는 것보다 효율적이다.
최대 힙 만들기
heap_items = [1, 3, 5, 7, 9]
max_heap = []
for item in heap_items:
heapq.heappush(max_heap, (-item, item))힙에 원소를 추가할 때, (-item, item)의 튜플 형태로 넣어주면 튜플의 첫번째 원소를 우선순위로 힙을 구성하게 된다.
item이 큰 수 일수록 부호를 반전하면 작은 수가 되기 때문에 max_heap자체는 최소 힙으로 구현이 되겠지만,
각 튜플의 두번째 인덱스를 사용하면 최대 힙처럼 사용할 수 있게 되는 것이다.
# 구현된 max_heap
[(-9, 9), (-7, 7), (-3, 3), (-1, 1), (-5, 5)]파이썬 API : https://docs.python.org/ko/3/library/heapq.html#heapq.heapify
heapq — 힙 큐 알고리즘 — Python 3.11.0 문서
heapq — 힙 큐 알고리즘 소스 코드: Lib/heapq.py 이 모듈은 우선순위 큐 알고리즘이라고도 하는 힙(heap) 큐 알고리즘의 구현을 제공합니다. 힙은 모든 부모 노드가 자식보다 작거나 같은 값을 갖는
docs.python.org
[자료구조] 그림으로 알아보는 힙(Heap)
항상 공부하기로 한 힙(Heap) 자료구조를 이제야 정리하게 되었습니다. 대표적으로 우선순위 큐를 구현하는데 많이 사용한다고 알고만 있었지 정확히 어떤 자료구조인지 잘 몰랐습니다. 이번 기
velog.io
