우선순위 큐와 힙의 개념과 차이, 사용 사례를 설명합니다! 힙이 어떻게 동작하는지도 예를 통해 자세히 설명합니다!

https://youtu.be/P-FTb1faxlo

우선순위 큐(Priority queue)

- 큐와 유사하지만 우선순위가 높은 아이템이 먼저 처리됨

- 주요 동작 : insert, delete, peek

  

힙(Heap)

- 주로 이진 트리 기반으로 구현

-- 트리(tree) : 부모-자녀처럼 계층적인 형태를 가지는 구조

-- 이진 트리(binary tree) : 자녀가 최대 두 개인 트리

- max heap : 부모 노드의 키가 자식 노드(들)의 키보다 크거나 같은 트리

- min heap : 부모 노드의 키가 자식 노드(들)의 키보다 작거나 같은 트리

- 주요 동작 : insert, delete, peek

  

Priority queue와 Heap의 관계

힙의 키를 우선순위로 사용한다면 힙은 우선순위 큐의 구현체가 된다.

Priority queue = ADT(Abstract Data Type) => 개념O, 구현X

Heap = data structure => 구현까지 O

Priority queue에는 여러 구현체들이 있을 수 있지만 Heap이 가장 성능이 좋아 많이 사용된다. 그러나 둘은 다른 개념이다.

  

Priority queue와 Heap의 사용

- 프로세스 스케줄링

- heap sort(힙 정렬)