우선순위 큐(Priority Queue)

우선순위 큐는 각 요소가 우선순위를 가지며, 높은 우선순위를 가진 요소가 먼저 처리되는 자료구조이다.

우선순위 큐는 삽입과 삭제를 중점적으로 사용하는 자료구조이다.

따라서 특정 값을 가진 원소를 검색할 수 있는 기능이 필요없다.

힙(Heap) 자료구조는 우선순위 큐를 구현하기 위한 자료구조로 사용된다.

최대 힙(Max-Heap)과 최소 힙(Min-Heap)

• 최대 힙 : 부모 노드가 자식 노드보다 크거나 같은 값을 갖는 완전 이진 트리
  • 루트 노드에 가장 큰 값이 위치한다.
• 최소 힙 : 부모 노드의 값이 자식 노드의 값보다 작거나 같은 완전 이진 트리
  • 루트 노드에 가장 작은 값이 위치한다.

포화 이진 트리와 완전 이진 트리

• 포화 이진 트리
  • 모든 레벨이 완전히 채워진 이진 트리
  • 노드의 개수는 2^k - 1개이다.
  • 모든 노드가 정확히 2개의 자식 노드를 가진다.
• 완전 이진 트리
  • 마지막 레벨을 제외한 모든 레벨이 완전히 채워진 이진 트리
  • 마지막 레벨의 노드들은 왼쪽부터 순서대로 채워진다.

힙(Heap)을 만족하는 2가지 조건

1. 완전 이진 트리