chater2 Max(Min) Heap

Max(Min) Heap Definition

정의 1 : max(min) heap은 internal node(child node가 존재하는 node)가 그들의 children보다 작지(크지) 않은 완전이진트리를 말한다.

정의 2 : root node가 각각의 child 보다 작고(크고) 각각의 child를 root node로 갖는 subtree들은 max(min) heap 의 특징을 가지고 있다. max(min) heap은 max(min)heap 특징을 지닌 완전이진트리이다.

Priority Queue에서 delete와 insert가 돌아가는 과정

insert code 시험대비

delete code 시험대비

Priority Queue는 insert와 delete가 모두 O(log n)으로 insert와 delete가 모두 빈번하게 나오는 경우 훨씬 효율적이다.

---

Heap Sort

방법

1. 배열 n의 정렬되지 않은 요소들을 max heap으로 만든다.

2. max heap에서 요소들을 추출하여 정렬된 배열을 만든다.

heap sort sudo code

unordered array를 Max heap으로 바꿔주는 과정이다. n이 제일 작은 internal node를 root로 갖는 subtree부터 Max heap으로 바꿔주면서 모든 internal 노드를 Max heap으로 바꿔준다. 부모노드가 자식노드보다 작을 경우 자식노드의 값이 부모노드로 가고 부모노드의 값이 자식노드로 가서 Max heap에서 delete와 같은 방식으로 자신보다 작은 값을 만날 때까지 내려간다.

max heap을 만드는데 O(n) 그리고 max_heap을 모두 delete하여 ordered list를 만드는데 O(nlogn)이므로 총 O(n+nlogn) = O(nlogn)이 된다.

adjust sudo code

make max heap의 시간복잡도 증명

만들어진 max-heap에서 정렬된 알고리즘을 만드는 과정이다. 마지막 노드와 루트노드의 위치를 바꾸고 n-1번째까지만 max heap을 만들어주는 과정을 반복한다.

한 칸씩 정렬 될 때마다 루트노드가 리프노드까지 이동하므로 한 번 extraction이 일어날 때 시간 복잡도는 O(logn)이다.