우선순위 큐(Priority queue)

우선순위 큐(Priority queue)

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

우선순위 큐 주요 동작

insert

큐에 아이템을 집어 넣는 역할을 한다. "아이템에 우선순위 정보도 같이 넣어줘야 한다"

delete

가장 우선순위가 높은 아이템을 제거 해주는 역할 한다.

peek

delete와 비슷하지만 우선순위에서 제거는 하지 않음

힙 (Heap)

힙은 주로 이진트리 기반으로 구현 한다

여기서 트리란 부모-자녀처럼 계층적인 형태를 가지는 구조를 말한다

"이진트리" 자녀가 최대 두 개인 트리

힙의 종류

최대 힙 (Max heap)

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

최소 힙 (Min heap)

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