Priority queue(우선순위 큐)
큐와 유사하지만 우선순위가 높은 아이템이 먼저 처리됨
-insert : 집어넣는다(우선순위 정보도 같이)
-delete : 가장 우선 순위가 높은 아이템을 빼낸다.
-peek : delete와 유사하지만 우선순위 큐에서는 제거하지 않는다.
Heap
주로 이진트리(binary tree)기반으로 구현 / 힙은 max heap과 min heap
-insert : 집어넣는다(아이템 key값도 같이)
-delete : maxheap이라면 key값이 가장 큰 아이템을 반환
minheap이라면 key값이 가장 작은 아이템을 반환
-peek : delete와 유사하지만 실제로 heap에서 꺼내지 않는다
트리 :부모-자녀처럼 계층적인 형태를 가지는 구조
이진트리 : 부모가 자녀를 최대 두개만 가질 수 있는 트리
max heap : 부모 노드의 키(key)가 자식 노드(들)의 키(key)보다 크거나 같은 트리
min heap : 부모 노드의 키(key)가 자식 노드(들)의 키(key)보다 작거나 같은 트리
Priority queue 와 Heap의 관계
힙(heap)의 키(key)를 우선순위(priority)로 사용한다면 힙은 우선순위 큐(priority queue)의 구현체가 된다.
Priority queue = ADT (After data type)
-실제로 구현을 설명하지 않음
-어떤 동작들이 있는지 개념적인것만 설명
Heap = data structure
-구현까지 있는거
그래서 결국 Heap을 Priority queue에 구현체라고 많이들 표현함
사실 Priority queue에는 많은 구현체들이 있지만 Heap이 제일 성능이 좋기때문에 대부분 많이 쓰기 때문에
'Priority queue랑 Heap이랑 똑같다' 라는 인식이 조금 생겼지만 엄밀히 놓고 보면 서로 다른 개념이다.
사용사례
-프로세스 스케줄링(process scheduling)
-heap sort(힙 정렬)
※힙(heap) 메모리의 힙은 위에 적힌 힙과는 관련 없음
