현업에서 구현할 일은 잘 없음.
하지만 개념과 사례를 알면, 기술 문서를 읽을 때 도움이 될 수 있음.

개념

우선순위 큐(Priority queue)

• 큐(Queue)와 유사함
• 우선순위가 높은 아이템이 먼저 처리되는 큐

우선순위 큐 주요 동작

• insert: 아이템을 우선순위 정보와 함께 넣음
• delete: 최(!)우선순위 아이템을 빼냄
• peek: delete와 유사하지만, 제거는 안함

힙(Heap)

• 힙은, 주로 이진 트리(binary tree) 기반으로 구현
  *트리: 계층적인 구조(ex. 부모-자녀 관계)
  **이진 트리: 자녀가 0~2개인 트리
• 힙의 2종류
  • max heap:
    부모 노드의 key가 자식 노드(들)의 key보다 크거나 같은 트리
  • min heap:
    부모 노드의 key가 자식 노드(들)의 key보다 작거나 같은 트리

힙 주요 동작

• insert: 아이템과 key를 넣음 (max heap / min heap)
• delete: 아이템과 key를 빼냄 (max heap / min heap)
• peek: delete와 유사하지만, 제거는 안함 (max heap / min heap)

차이

힙(heap)의 key를 우선순위(priority)로 사용한다면,
힙(heap)은 우선순위 큐(Priority queue)의 구현체가 된다.
(가능한 구현체 중에서 '힙'이 가장 성능이 좋아서 많이 씀)

Priority queue = ADT
Heap = Data Structure

사례

프로세스 스케줄링(process scheduling)

• CPU를 쓰려고 ready queue에서 대기하고 있는 프로세스1, 2, 3, ..., etc

힙 정렬(heap sort)

힙 메모리의 힙 != 오늘 배운 힙