[ch 09-1] 우선순위 큐의 이해

[우선순위 큐의 개념]

- 기존 큐와 다르게 데이터가 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 꺼내짐

- 데이터에 우선순위가 별개로 지정되지 않으며 값을 기준으로 순서가 동적으로 지정

  ※ 데이터 값의 오름차순 또는 내림차순으로 기준을 잡을 수 있으며, 개발자가 결정

- 구현 방법에는 '배열, 연결 리스트, 힙'이 있음

[배열과 연결 리스트 구현 시 문제점]

■ 배열

- 데이터의 우선순위가 높을수록 배열의 앞쪽에 위치시킴

- 우선순위가 높은 데이터의 반환과 소멸이 쉬움

★ 데이터를 삽입 및 삭제하는 과정에서 데이터를 한 칸씩 앞으로 또는 뒤로 옮기는 연산이 필요

★ 삽입의 위치를 찾기 위해서 모든 데이터와 우선순위를 비교하면서 진행해야 함

■ 연결 리스트

★ 배열과 다르게 데이터 위치를 옮기는 작업은 없으나 삽입의 위치를 찾기 위해서 첫 번째 노드부터 마지막 노드까지

    데이터, 우선순위 비교를 진행해야 함

[힙] 

※ Heap: 무엇인가를 차곡차곡 쌓아 올린 더미

- 완전 이진 트리로 구성됨

- 모든 노드는 자식 노드의 데이터 값 보다 같거나 커야 함

  ※ 숫자가 낮을수록 우선순위가 높다고 가정

■ 그림(최대 힙) max heap

- 루트 노드로 올라갈수록 저장된 값이 커지는 완전 이진 트리

■ 그림(최소 힙) min heap

- 루트 노드로 올라갈수록 저장된 값이 작아지는 완전 이진 트리