[자료구조] 우선순위 큐와 힙

큐 vs 우선순위 큐

• 큐
  • 먼저 들어온 데이터가 먼저 나가는 선입선출 (FIFO) 방식
• 우선순위 큐
  • 들어간 순서에 상관없이, 우선순위가 높은 데이터 먼저 나오는 것
  • 우선순위가 높은 요소는 우선순위가 낮은 요소보다 먼저 큐에서 제외됨
  • 두 요소의 우선순위가 같으면 큐의 순서에 따라 제공됨
• 우선순위 큐는 힙(Heap)이라는 자료구조를 통해 구현될 수 있음 (배열, 연결리스트도 가능하지만 비효율적)
  • 엄밀히 말하자면, 배열을 사용해서 힙을 구현하고, 그 힙으로 우선순위 큐를 구현함
  • 힙은 루트 노드에 우선순위가 높은 데이터를 위치시키는 자료구조임
  • 또한 힙은 완전 이진 트리임
  • enqueue, dequeue를 통해 구현 가능 (우선순위 큐에서 데이터를 삽입, 꺼내는 행위)