우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조
우선순위 큐 | 구현 방식 | 삽입시간 |
---|---|---|
리스트 | O(1) | O(n) |
힙(Heap) | O(nlogn) | O(nlogn) |
완전 이진트리 기반의 자료구조이다.
최대값, 최소값을 빠르게 구하기 위해서 사용
max heap(최상단 노드가 최대값), min heap(최상단 노드가 최소값) 두 종류가 존재
시간 복잡도
동작 | 시간복잡도 |
---|---|
삽입 | O(logn) |
삭제 | O(logn) |
최소or최대값을 검색 | O(1) |
이진트리 기반의 최소 힙(min heap) 자료구조를 다룰 수 있는 함수를 제공하는 파이썬 내장 라이브러리
import heapq
heapq.heapify(heap)
heapq.heappush(heap, value)
heapq.heappop(heap)
heap[0]
삽입 : heapq.heappush(heap, -value)
제거 : -heapq.heappop(heap)
import heapq
def heapsort(iterable):
h = []
result = []
for value in iterable:
heapq.heappush(h, value)
for i in range(len(h)):
result.append(heapq.heappop(h))
return result
result = heapsort([1,3,5,7,9,2,4,6,8,0])
print(result)
참고 링크
https://www.geeksforgeeks.org/difference-between-min-heap-and-max-heap/