우선순위 큐
: 우선순위의 개념을 큐에 도입
→ 우선순위가 높은 데이터가 먼저 나감
- 시뮬레이션, 스케줄링, 수치해석
- 배열, 연결리스트, 힙으로 구현(힙이 가장 효율적) → 힙 : 삽입(O(logN)), 삭제(O(logN))
개념
: 우선순위 큐를 위해 만들어진 자료구조
- 완전 이진 트리의 일종 → 최소값과 최대값을 빠르게 찾도록 만들어진 자료구조
- 반정렬 상태
- 힙 트리는 중복된 값 허용 ( 이진 탐색 트리는 중복값 허용 X)
종류
최대힙
: 부모 노드의 키 ≥ 자식 노드의 키
최소힙
: 부모 노드의 키 ≤ 자식 노드의 키
구현
- heaqp.heappush(heap, item) : item을 heap에 추가
- heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & return
- heapq.heapify(x) : 리스트 x를 heap으로 변환 (O(N))
힙 생성 & 원소 추가, 삭제
import heapq
heap = []
heapq.heappush(heap, 50)
heapq.heappush(heap, 10)
heapq.heappush(heap, 20)
=> [10, 50, 20]
heapq.heappop(heap)
=> [20, 50]최대 힙 구현
heap_items = [1, 3, 5, 7, 9]
max_heap = []
for item in heap_item:
heapq.heappush(max_heap, (-item, itemm))
=> [(-9, 9), (-7, 7), (-3, 3), (-1, 1), (-5, 5)]