9.1. 우선순위 큐 추상 데이터 타입

우선순위 큐의 소개

• 예를 들면, 네트워크 패킷 중에서도 네트워크 관리와 관련된 패킷은 다른 패킷보다 우선순위를 가진다.
• 또한, 운영체제 중에서도 시스템 프로세스는 응용 프로세스보다 더 우선순위를 가지게 된다.
• 우선순위 큐는 사실 가장 일반적인 큐라고 할 수 있는데, 왜냐하면 스택이나 큐도 우선순위 큐를 사용하여 얼마든지 구현할 수 있기 때문이다.
  • 사실상 어떤 걸 우선순위 기준으로 두느냐..만 정의한 것이다.
• 우선순위 큐는 컴퓨터의 여러 분야에 이용되는 데, 대표적으로 시뮬레이션 시스템 (여기서의 우선순위는 대개 사건의 시각이다.), 네트워크 트래픽 제어, 운영 체제에서의 작업 스케줄링, 수치 해석적인 계산 등에 사용된다.

9.2. 우선순위 큐의 구현 방법

1. 배열을 이용한 방법

1. 정렬이 안 되어 있을 경우
   • 배열의 맨 끝에 새로운 요소를 추가하면 된다. : O(1)
   • 삭제의 경우, 위치를 찾은 다음 + 이동까지 시키는 비용이 존재한다 : O(n)
2. 정렬이 되어 있을 경우
   • 삽입할 위치를 찾고, 요소를 이동해야 한다. : O(n)
   • 삭제의 경우는, 그냥 끝에 있는 것을 삭제하면 된다 (우선순위에 따라 정렬이 되어 있으므로) : O(1)

2. 연결리스트를 이용한 방법

• 연결리스트의 경우, 사실상 리스트에서 이동시키는 비용만 제거한 것이다.
• 즉, 리스트와 시간 복잡도는 전부 같고, 이동에 대한 부담이 덜어졌다는 차이점이 존재한다.

3. 히프 (heap)를 이용한 방법

• 우선순위 큐를 위해 구현된 자료구조이다. 다음의 챕터에서 자세히 살펴본다.

9.3. 히프

히프의 개념

• 히프는 여러개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아낼 수 있도록 만들어진 자료구조이다. 히프는 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진 트리를 말한다.