우선순위 큐와 힙의 개념과 차이, 사용 사례를 설명, 힙의 동작 방식

Priority queue(우선순위 큐)

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

우선순위 큐 주요 동작

• insert
• delete
• peek

Heap (힙)

힙은 주로 이진트리(Binary Tree) 기반으로 구현

*트리란 부모-자녀처럼 계층적인 형태를 가지는 구조, 이진 트리는 자녀가 최대 두 개인 트리

힙은 Max Heap과 Min Heap으로 나뉨.

Max heap

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

min heap

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

Heap 주요 동작

• insert

• delete

• peek

Heap 실습

자세한 내용은 영상을 참조.

Priority queue와 Heap의 관계

힙(Heap)의 키(Key)를 우선순위(Priority)로 사용한다면 힙은 우선순위 큐(priority queue)의 구현체가 된다.

Priority queue = ADT (Abstract Data Type, 추상데이터) : 동작만 설명
Heap = data structure : 구현까지 함

엄밀히 따지면 Priority queue 와 Heap은 다르다.

Priority queue와 Heap의 사용사례

1. 프로세스 스케쥴링 (Process scheduling)
2. 힙 정렬 (heap sort)

힙(heap) 메모리의 힙은 오늘 배운 힙과는 관련 없음

heap 자체가 사전적인 의미로 쌓여있는. 이런 뜻이므로...