[C++] 우선순위 큐

• 순서
  1. 큐란?
  2. 우선순위 큐란?
  3. 우선순위 큐 구현방법
  4. 힙이란?
  5. 힙의 특징과 종류
• 큐란?
  1. 큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out)형식의 자료구조
• 우선순위 큐란?
  1. 우선순위 큐(Priority Queue)는 먼저 들어오는 데이터가 아닌, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조
  2. 일반적으로 힙(Heap)을 이용하여 구현함
• 우선순위 큐 구현방법
  1.  
• 힙이란?
  1.  힙은 우선순위 큐를 위해 고안된 완전 이진 트리 형태의 자료구조
  2. 여러 개의 값 중 최댓값 또는 최솟값을 찾아내는 연산이 빠름
• 힙의 특징과 종류
  1. 힙의 특징
     • 완전 이진 트리 형태로 이루어져있음
     • 부모 노드와 서브 트리간 대소 관계가 성립됨.(반정렬 상태)
     • 이진 탐색 트리와 달리 중복된 값이 허용됨
  2. 힙의 종류
     • 최대 힙: 부모 노드의 키 값이 자식 노드보다 크거나 작은 완전 이진 트리이다.
     • 최소 힙: 부모 노드의 키 값이 자식 노드보다 작거나 같은 완전 이진 트리이다.