complete binary tree 를 사용한다.
마지막 level를 제외한 모든 level는 모두 채워져 있고, 마지막 level은 왼쪽에서부터 채워지는 구조

max-heaps and min-heaps 이 있다.

max-heap

A[PARENT(i)] $\ge$ A[i]

부모 노드가 그것의 자식 노드보다 크거나 같다.
루트 노드가 가장 크다.

min-heap

A[PARENT(i)] $\le$ A[i]

부모 노드가 그것의 자식 노드보다 작거나 같다.
루트 노드가 가장 작다.

기본 설정

A라는 배열이 있을 때, A[1]이 root node이다.
모든 요소들은 level order로 저장된다.

구조체를 사용해도 되지만 배열을 사용하는 것이 편리하기 때문에 배열을 사용한다.

Max Heap sort

Heap sort 표현법

배열에서 노드 표현

parent: $\lfloor \frac{i}{2} \rfloor$
left child: $2i$
right child: $2i + 1$

i는 현재 노드의 인덱스

Height of heap

n개의 숫자가 있을 때, heap은 complete binary tree의 형태로 이루어져 있기 때문에 $\theta(logn)$ 이다.

Max-Heapify

1. Input: 삽입된 숫자를 제외하고 나머지는 max-heap으로 구성되어 있다.
2. 따라서 Input에 해당하는 subtree만 조정하면 된다.
3. Input의 left / right child 중 더 큰 것을 골라 Input과 위치를 바꾼다.
4. Input의 새로운 위치에 대해 max-heap이 성립할 때까지 (3)의 과정을 반복한다.

Running time of MAX-HEAPIFY

• $\theta(1)$: 두 숫자 교환하는데 걸리는 시간
• $\theta(logn)$: worst case에는 tree 전체를 변환해야하기 때문에 heap의 height 만큼 소요된다.
• $\theta(1)$: best case에는 삽입된 위치가 올바른 위치인 경우이기 때문에 $\theta(1)$이다.

Build Max Heap

pseudocode of Build Max Heap

A는 정렬이 되지 않고 숫자가 들어있는 배열이다.

BUILD-MAX-HEAP(A)
	A.heap-size= A.length
    for i= ⌊A.length/2⌋ downto 1 
    	MAX-HEAPIFY(A, i)

⌊A.length/2⌋는 자식이 있는 가장 큰 node의 인덱스이다.

Running time of build heap

• Upper bound
  • Each call to MAX-HEAPIFY costs O(logn) time, and there are O(n) such calls, Thus, the running time is O(nlogn)
• Tigher upper bound
  • MAX-HEAPIFY의 시간 복잡도는 트리의 높이를 따라간다. 이때, 최고 높이의 노드의 개수는 한정적이므로 더 타이트하게 upper bound를 설정할 수 있다.
  • n개의 숫자가 있을 때, height(h)는 ⌊logn⌋이고, 한 높이(레벨)에서의 최대 노드 개수는 $\left\lceil \frac{n}{2^{h+1}} \right\rceil$ 이다.

Running time of Tigher upper bound

1. $\sum_{h=0}^{\lfloor \log n \rfloor} (\left\lceil \frac{n}{2^{h+1}} \right\rceil \cdot O(h))$ = $O\left( \sum_{h=0}^{\lfloor \log n \rfloor} \frac{n}{2^{h+1}} \cdot h \right)$

2. $\sum_{h=0}^{\lfloor \log n \rfloor} (\frac{h}{2^{h+1}})$

3. $\sum_{h=0}^{\infty} \frac{h}{x^h} = \frac{x}{(x-1)^2} \quad \text{(for \( |x| > 1 \))}$ 이므로 $\sum_{h=0}^{\lfloor \log n \rfloor} (\frac{h}{2^{h+1}})$ = 2

4. 따라서 $O\left( \sum_{h=0}^{\lfloor \log n \rfloor} \frac{n}{2^{h+1}} \cdot h \right)$ = $O(n)$ 이다.

Tighter upper bound에서 우리는 linear time에 정렬할 수 있다.

Extract-Max

1. 최대 노드를 (max heap에서는 루트 노드) 제거한다.
2. Heap을 재구성한다.

Restruct max heap

1. 루트 노드를 제거한다.
2. 가장 마지막 인덱스의 숫자를 루트 노드로 이동시킨다.
3. 루트 노드부터 MAX-HEAPIFY를 진행한다.

Running time of extract-max

1. 전체 노드를 제거해야한다: $O(n)$
2. (1)의 각 과정에서 MAX-HEAPIFY를 진행한다.: $O(nlogn)$

Total running time of extract-max: $O(nlogn)$

pseudocode of heap sort

HEAPSORT(A)
	BUILD-MAX-HEAP(A)
    for i=A.length downto 2 
    	exchange A[1] with A[i] //마지막 노드를 루트 노드로 이동
    	A.heap-size= A.heap-size-1
    	MAX-HEAPIFY(A, 1) //루트 노드부터 진행

Running time of heap sort

1. Running time of BUILD-MAX-HEAP(A): $O(n)$
2. Running time of EXTRACT-MAX: $O(nlogn)$

Total running time of heap sort: $O(n)$ + $O(nlogn)$ = $O(nlogn)$

Priority queue

각 요소에 KEY라고 불리는 값이 연관된 요소 집합 S를 유지하는 데이터 구조
우선 순위가 있는 KEY를 먼저 처리하는 Queue

Priority queue operation

최대 우선 순위 큐의 연산은 다음과 같습니다:

INSERT(S, x): 요소 x를 집합 S에 삽입
MAXIMUM(S): 집합 S에서 가장 큰 키를 가진 요소를 반환
EXTRACT-MAX(S): 집합 S에서 가장 큰 키를 가진 요소를 제거하고 반환
INCREASE-KEY(S, x, k): 요소 x의 키 값을 새로운 값
k로 증가

Running time of priority queue operation

MAXIMUM: Read the max value

• $O(1)$

EXTRACT-MAX: Remove the max value + MAX-HEAPIFY

• $O(log n)$

HEAP-INCREASE-KEY: MAX-HEAPIFY after changing value of key

• $O(log n)$

INSERT: MAX-HEAPIFY after insertion

• $O(logn)$ time

pseudocode of max-priority-queue-insert

MAX-HEAP-INSERT(A, key)
	A.heap-size= A.heap-size+ 1
	A[A.heap-size] = −∞ // A.heap-size+ 1의 공간을 확보하기 위해 임의로 굉장히 작은 값을 할당
	HEAP-INCREASE-KEY(A, A.heap-size, key)