우선순위 큐(Queue)

우선순위 큐(Queue)란, 우선순위 개념을 큐에 도입한 자료구조이다.

• 우선순위 큐(Queue): 가장 우선순위가 높은 데이터부터 삭제된다.
• 큐(Queue): 가장 먼저 들어온 데이터부터 삭제된다.
• 스택(Stack): 가장 최근에 들어온 데이터부터 삭제된다.

힙(Heap)

힙(Heap)이란, 완전 이진 트리(Complete Binary Tree)의 일종으로, 우선순위 큐를 위해 만들어진 자료구조이다.

여러 개의 값들 중에서, 최대값이나 최소값을 빠르게 찾아내도록 만들어진 자료구조이다.

*완전 이진 트리란, 마지막 레벨을 제외한 나머지 모든 레벨에서 노드가 완전히 채워진 트리를 말한다. 또한, 마지막 레벨은 꽉 차 있지 않아도 되지만, 노드가 왼쪽에서 오른쪽으로 채워져야 한다.

힙(Heap)의 종류

• 최대 힙(max heap)
  • 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리

• 최소 힙(min heap)
  • 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리

출처: ypes of Heap