우선순위 큐
일반적인 큐는 선입선출 인데
우선순위 큐는 들어간 순서 상관없이 우선순위가 높은 데이터가 먼저 나오는 것을 말한다.
속성
모든 항목에는 우선순위가 있다.
우선순위가 높은 요소는 우선순위가 낮은 요소보다 먼저 queue에서 제외가 된다.
두 요소의 우선순위가 같으면 queue의 순서에 따라 제공된다.
Heap 힙이란?
우선순위 큐를 위해 고안된 완전 이진트리 형태의 자료구조
여러 개의 값 중 최댓값 또는 최솟값을 찾아내는 연산이 빠름
힙의 종류
최대힙 (max heap)
부모 노드의 키 값이 자식 노드보다 크거나 같은 완전 이진 트리
key(부모노드) >= key(자식노드)
최소 힙 (min heap)
key(부모노드) <= key(자식노드)
자식노드를 구하고 싶을때
왼쪽 자식노드index = (부모 노드 index)2
오른쪽 자식노드index = (부모 노드 index)2+1
부모노드를 구하고 싶을때
부모노드 index = (자식노드index)/2
힙큐 모듈 사용하기
힙 property : A가 B의 부모노드이면 A의 키값과 B의 키값 사이에는 대소 관계가 성립한다
최소 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙
최대 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙
<출처: https://www.geeksforgeeks.org/heap-data-structure/minheapandmaxheap/>
힙 함수 활용하기
heapq.heappush(heap, item) : item을 heap에 추가
heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴. 비어 있는 경우 IndexError가 호출됨.
heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환함 (in linear time, O(N) )
힙 생성, 추가
import heapq
heap=[]
heapq.heappush(heap,50)
heapq.heappush(heap,35)
heapq.heappush(heap,10)
print(heap)[10, 50, 35]
heappop 함수는 가장 작은 원소를 힙에서 제거함과 동시에 그 결괏값으로 리턴
result = heapq.heappop(heap)
print(result)
print(heap)10
[35, 50]
삭제하지않고 가져오고싶다면 [0] 인덱싱을 통해 접근
이미 있는곳에서 힙
heap2= [33,56,88]
heapq.heapify(heap2)
print(heap2)[33, 56, 88]
