해당 글은 Algorithms. by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani를 정리한 스터디 노트입니다.해석하면서 정리한 글입니다.

4.5 Priority queue implementations

4.5.1 Array

우선 순위 큐의 가장 간단한 구현 모든 잠재적 요소에 대한 키 값의 순서가 지정되지 않은 배열(Dijkstra 알고리즘의 경우 그래프의 꼭지점)입니다. 처음에는 이 값을 $∞$로 설정합니다.
insert와 decreasekey는 $O(1)$로 속도가 빠릅니다.

• 키 값 조정만 수반하기 때문에 빠릅니다. 반면에, deletemin은 list의 linear-time scan이 필요합니다.

4.5.2 Binary heap

여기서 요소는 전체 이진 트리, 즉 각 level이 왼쪽에서 오른쪽으로 채워지는 이진 트리에 저장되며 다음 level이 시작되기 전에 가득 차야 합니다.
게다가 특수한 순서 제약이 적용됩니다.

• 트리의 모든 노드의 키 값이 하위 노드의 키 값보다 작거나 같습니다. 따라서 루트에는 항상 가장 작은 요소가 포함됩니다. 어래 그림을 참조해보겠습니다.

insert를 하기 위해선, 트리 맨 아래(사용 가능한 첫 번째 위치)에 새 요소를 배치하고 “bubble up”이 발생하도록 해야합니다. 즉 parent 보다 작은 경우, 두 개를 swap하고 이를 반복합니다. (figure b-d)
swap 횟수는 최대 트리 높이이며, 요소가 n개일 때, $log_2n$입니다.
decreasekey는 요소가 이미 트리에 있기 때문에, 현재 위치에서 bubble up이 일어나도록 해야합니다.

**deletemin$$을 하기 위해선, 루트 값을 반환해야 합니다.
그런 다음, heap에서 이 요소를 제거하고 트리의 마지막 노드(바닥의 오른쪽 맨 끝 노드) 를 루트에 배치시킵니다.
다음으로 “sift down”을 합니다

• 어느 child보다 클 경우, 작은 child와 swap하고 이를 반복합니다.(figure e-g)
  이 경우에도 시간 복잡도는 $O(nlogn)$입니다.

Reference

1.Algorithms. by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani(http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf)