우선순위 큐
우선순위 큐는 우선 순위의 개념을 큐에 도입한 자료구조이다.
응용되는 사례는 다음과 같다.
- 시뮬레이션 시스템
- 네트워크 트래픽 제어
- 운영 체제에서의 작업 스케쥴링
- 수치 해석적인 계산
우선순위 큐는 여러 방법으로 구현이 가능한데, 가장 효율적인 구조는 heap이다.
Heap
- 완전 이진 트리의 일종으로 우선순위 큐를 위하여 특별히 만들어진 자료 구조
- 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료 구조
특징으로는 느슨한 정렬 상태를 유지한다.
추가로 중복된 값을 허용한다.
Heap의 종류
-
최대 히프(max heap)
부모노드 >= 자식노드
-
최소 히프(min heap)
부모노드 <= 자식노드
Heap의 구현
히프는 완전 이진 트리이기 때문에 각각의 노드의 차례대로 번호를 붙일 수 있다. 따라서 히프를 저장하는 표준적인 자료구조는 배열이다.
- 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
- 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
- 부모의 인덱스 = (자식의 인덱스) / 2
Heap의 복잡도 분석
삽입, 삭제의 시간 복잡도 : O(log n)
Heap 정렬
- 히프의 특성을 이용하여 삽입 삭제만으로 정렬 가능
Heap 정렬의 복잡도
- O(n log n)
히프 정렬은 전체 자료를 정렬하는 것이 아니라 가장 큰 값 몇 개만 정렬 할 때 가장 유용하다.
허프만 코드
최소 히프를 이용하여 구현
