Lec 02

Mathematical Induction

Base Case: P(1) 또는 P(0)이 참임을 보인다.

Inductive Step:

P(k)이 참이라고 가정하고, 이로부터 P(k+1)이 참임을 증명한다.

Proof of Correctness

입력 전 조건 (Precondition) — 알고리즘 시작 시 참이어야 하는 조건

루프 불변식 (Loop Invariant) — 반복문이 돌 때마다 항상 유지되는 조건

종료 후 조건 (Postcondition) — 알고리즘 종료 시 문제의 요구사항이 만족됨

PQ

array impl

int PQdel(){
	int j, min =0;
	for(j=1; j<N; j++){
		if(less(pq[min],  pq[j]))
			min = j;
	swap(pq[min], pq[N-1]);
	return pq[--N];
}

시간복잡도 N짜리. 공간도 미리 잡아둬야함.

init = O(N) , push = O(1)

min heap

def

– A max(min) heap is a complete binary tree where the key value in each
internal node is no smaller(larger) than the key values in its children.

deletion

full binary tree 형태를 유지하기 위해서

맨 뒤의 원소를 최상단으로 swap.

안정된 상태를 유지할 때까지 fixDown.

마지막 원소를 return.

fixDown ⇒ 자식= 부모인덱스*2 or 부모인덱스*2 +1

내릴 때는 두 자식 중 더 큰 놈이랑 바꿔주는게 맞음.

insert

맨 뒤에 삽입.

안정된 상태가 될때까지 fixUp

fixUp ⇒ 부모 = 자식인덱스/ 2.

Make max heap Process

heap sort의 개괄적인 큰 그림

// make max heap
for(i = n/2 ; i > 0 ; i--) // 자식노드가 있는 최대 인덱스 노드는 n/2임.
	adjust (list, i, n);
// extract items one by one
for(i = n-1; i>0 ; i--){ // 힙에서 최댓값을 하나씩 꺼내서 맨 뒤에 저장
	swap(list[1], list[i+1]);
	adjust(list, 1, i);
}

adjust func

ADJUST(A, i, n):
1  L ← left(i);  R ← right(i)            // i의 두 자식 인덱스
2  largest ← i                            // 일단 i가 가장 큰 것으로 가정
3  if L ≤ n and A[L] > A[largest]:        // 왼쪽 자식이 존재하고 더 크면
4      largest ← L
5  if R ≤ n and A[R] > A[largest]:        // 오른쪽 자식도 검사
6      largest ← R
7  if largest ≠ i:                        // 자식 중 하나가 더 크다 → 힙 위반
8      swap A[i], A[largest]              // 부모/자식 교환
9      ADJUST(A, largest, n)              // 깨졌을 수 있는 아래쪽 서브트리로 재귀
10 // else: 자식보다 부모가 크거나 같음 → 이미 힙 만족, 종료

3–6행: 존재하는 자식들 중 가장 큰 노드를 largest로 갱신. 이때 “왼/오른 서브트리 자체는 이미 힙”이라는 전제가 핵심이라, 부모-자식 관계만 바로잡으면 그 아래 서브트리가 무너질 가능성만 추적하면 됨.

•

한 번의 ADJUST 호출은 루트(현재 노드)에서 시작해 한 갈래로만 내려간다.

•

각 레벨에서 하는 일은 상수(두 자식 비교 최대 2회 + 필요 시 1회 스왑).

•

따라서 최대 레벨 수 = 트리 높이 d이고, 총 작업량은 O(1)×d = O(d). 강의노트 표기와 동일.

•

보통 완전이진트리에서 높이 d = ⌊log₂ n⌋이므로 최악은 O(log n)

신기한 점

for(i = n/2 ; i > 0 ; i--) // 자식노드가 있는 최대 인덱스 노드는 n/2임.
	adjust (list, i, n); // 시간복잡도 최악은 O(log n)

이 코드의 시간복잡도가 O(N)이다.

루트는 logN의 높이를 가지지만 leaf node 근처의 높이는 1정도이다.

이걸 공식으로 쓰면

T(n) = \sum_{h=0}^{\lfloor \log n \rfloor}
\frac{n}{2^{h+1}} \cdot O(h)
= O\!\left(
n \sum_{h=0}^{\infty} \frac{h}{2^{h}}
\right)

헷갈리면 표를 적으면 됨.

높이 h (루트에서 거리)	그런 노드 수	한 노드당 비용 (≈ O(h))	총비용
log n (루트)	1	O(log n)	O(log n)
log n − 1	2	O(log n − 1)	O(2 log n)
log n − 2	4	O(log n − 2)	O(4 (log n − 2))
…	…	…	…
1	n/2	O(1)	O(n/2)

make-heap의 정당성(proof of correctness)

for(i = n/2 ; i > 0 ; i--) // 자식노드가 있는 최대 인덱스 노드는 n/2임.
	adjust (list, i, n); // 시간복잡도 최악은 O(log n)

이 for 문에서 loop invariant : loop 를 시작하기 전에, 그 이전 인덱스 i 들(i+1, …, n)은 각각 max heap의 루트노드이다.

base step : i=n/2일 때 i+1, … , n은 leaf node. 자식노드가 없으니 힙조건 만족.

inductive step : i = k일 때 참이라고 가정. i=k-1일 때도 참임을 보이기.

k의 두 자식은 힙 구조 만족.

adjust func은 k를 힙의 루트로 만들어줄 것임.

adjust func은 하위 구조를 깨지 않기 때문에 k, …. ,n은 힙루트를 유지하고 있음.

→ k-1일때도 loop invariant가 성립.

PQ2 : min-max heap

Double-Ended Priority Queue

Insert(x), DeleteMin(), DeleteMax() — 세 연산 모두 O(log n) 목표

두 힙 방식: 하나는 min-heap, 하나는 max-heap을 두고 원소마다 “쌍방 인덱스”를 저장해 동기화.

•

장점: 단순 개념.

•

단점: 동기화/삭제 시 인덱스 갱신 코드가 귀찮고 캐시/메모리 locality가 애매.

Min-Max Heap: 단일 완전이진트리에서 레벨을 번갈아 min / max 레벨로 두고, 각 레벨의 불변식을 유지.

•

장점: 단일 배열로 깔끔, findMin/findMax 모두 O(1), 나머지 O(log n).

•

단점: 업/다운힙 시 “부모 vs 조부모(2레벨 간격)” 비교 규칙이 필요(구현 주의).

Min-Max Heap

invariant : min level 노드는 자기 서브트리의 최소값. max level 노드는 자기 서브트리의 최댓값.

기능 구현

A. Insert(x) — O(log n)

*말단(next hole)**에 x를 임시로 넣음(완전이진트리 유지).

현재 노드가 속한 레벨에 따라 비교 기준이 다름:

•

현재 노드가 min-level이면: 우선 부모가 존재하고 부모가 max-level인데 x > parent면 부모와 스왑 후, max-level 체인으로 조부모 방향(2칸 위) bubble-up 하며 x가 조부모보다 작지 않아야 함(즉 x ≤ 각 조부모의 자식 조건이도록 조정).

•

현재 노드가 max-level이면: 반대로 x < parent면 부모와 스왑 후, min-level 체인으로 조부모 방향 bubble-up 하며 x ≥ 각 조부모의 자식이 되도록 조정.

구현 팁: “부모와 1회 정합 후, 같은 부류끼리(=같은 레벨 성질끼리) 조부모 단위로 비교/스왑”이 핵심. (비교 횟수를 줄이고 레벨 불변식을 한 번에 맞춘다)

왜 2레벨씩? 레벨의 성질이

min↔max

같은 성질

두 단계 위

bubble-up은 2레벨 단위

B. DeleteMin() — O(log n)

*루트(전체 최소)**를 결과로 가져오고, 마지막 원소를 루트에 올린 뒤 힙 크기–.

루트는 min-level이므로 **“min-push-down”**을 수행:

•

자식+손자들 중 최소를 찾는다. (보통 손자 후보 4개까지 포함해 비교)

•

가장 작은 노드가 손자라면 루트와 스왑하고, **스왑된 손자 노드의 부모(=max-level)**와 **대소관계 위반 여부(손자가 부모보다 커야 함)**를 1회 보정 스왑.

•

가장 작은 노드가 자식이면 그 자식과 스왑.

•

이 과정을 더 이상 위반이 없을 때까지 반복.

핵심: min-level 노드는 자신의 서브트리 최소여야 하므로, 아래로 내려가며 손자까지 같이 보며 가장 작은 후보로 당겨온다. 동시에 중간에 지나치는 max-level 부모의 조건도 깨지지 않도록 한 번씩 보정.

C. DeleteMax() — O(log n)

findMax()는 보통 루트의 두 자식 중 더 큰 쪽(존재하면 그 인덱스를 imax)이므로, 그 위치를 결과로 꺼낸다.

말단 원소를 imax에 올리고 힙 크기–.

imax는 max-level이므로 “max-push-down”:

•

자식+손자들 중 최대를 찾는다(손자 4개 후보 포함).

•

가장 큰 노드가 손자면 스왑 후, 그 손자의 **부모(=min-level)**와의 **대소관계(부모 ≤ 자식)**를 1회 보정.

•

가장 큰 노드가 자식이면 그 자식과 스왑.

•

반복.

두 삭제 모두 “레벨 성질(min/max)을 만족시키며 2레벨 단위로 내린다”가 공통 패턴.

Leftist tree

왼쪽으로 구조적으로 치우친 형태의 pq.

•

Insert(x)

•

DeleteMin() → 이거도 좀 특이하게 루트노드 지우고 좌우 서브트리 머지로 간주해버림.

•

Merge(H1, H2)

를 log N 에 할 수 있음

make heap

bubble up

for (i = 0; i < n; i++)
    pq_insert(q, s[i]);   // 각 insert는 bubble_up

•

i번째 insert는 bubble_up (즉, 위로 올리기)을 수행.

•

이 때 bubble_up의 최대 깊이 = 현재 heap 높이 ≈ ⌊log₂(i)⌋.

•

따라서 전체 비용은

T(n) = \sum_{i=1}^{n} O(\log i)

= O(n \log n)

bubble down

for (i = q->n / 2; i >= 1; i--)
    adjust(q, i, q->n);   // bubble_down

•

leaf는 이미 힙 조건 만족하므로 무시.

•

i = n/2부터 1까지는 각 노드가 루트가 될 수 있는 “부분 트리(subtree)”의 높이에 따라

bubble_down의 비용이 log₂(하위 높이) 만큼만 걸림.

•

즉, 깊은 노드(leaf 근처)는 거의 움직이지 않음.

Made with Slashpage