Heapsort 1

Comparation

vs Insertion sort,
1. in-place.
2. running time is O(nlgn).

vs Merge sort,
1. running time is same as O(nlgn).
2. it does not require O(n) additional space.

-> Heap sort를 선택하는 대표 조건은 "추가 메모리를 거의 못 쓰면서도, 항상 O(nlgn) 성능을 보장해야 할 때" 이다.

Heap

배열 A에서

• A.length : the number of elements in the array
• A.heap-size : the number of elements in the heap
• only the elements in A[1...A.heap-size], where 0 <= A.heap-size <= A.length are valid elements of the heap.
• A[1] is the root of the tree
• index i가 있을 때
  • 2i : left child (if 2i <= A.heap-size)
  • 2i + 1 : right child (if 2i + 1 <= A.heap-size)
  • parent : floor(i/2)
• The height of a node is the number of edges on the longest simple downward path from the node to a leaf.
• Since a heap of n elements is based on a complete binary tree, its height is O(lgn).
• The height of the heap is the height of the root.

Max Heapify

시간복잡도 분석

• 어떤 노드 i를 루트로 하는 서브트리의 크기가 n이라고 하자.
• 즉, i 아래에 총 n개의 노드가 있다고 하자.
  -> 그럼 이 노드의 자식 중 하나가 가질 수 있는 최대 서브트리 크기는 얼마인가?

왜 subtree의 사이즈는 최대 2n/3을 못넘기는가?

높이가 0 ~ H-1인 완전이진트리가 있다고 하자.
전체 노드 수는 2^H - 1개.

높이가 1인 두 노드중 좌측 노드를 루트 노드로 하는 서브 트리를 LST라 하자. 
LST의 크기는 2^(H-1) - 1개.

LST에만 리프노드를 전부 채운다고 하면, 이 때 리프노드의 개수는 2^(H-1)개. 
전체 노드 개수와 LST에 리프노드 개수를 각각 더해주면
전체 노드 개수는 2^H - 1 + 2^(H-1) = 3/2 * 2^H - 1

LST의 개수는 2^H - 1

따라서
LST/전체노드개수 = 2^H - 1 / (3/2 * 2^H - 1) = 약 2/3

그래서 아래 문장도 설명된다.

• For a subtree of size n rooted at a given node i, the size of the subree rooted at a child of node i becomes maximum when the bottom level of the tree is exactly half full.

• 노드 i를 루트로 하는 사이즈 n짜리 서브트리에서의 수행 시간은 다음으로 이루어져 있다.

1. A[i], A[left], A[right] 정렬 - Theta(1).
2. T(2n/3) to recursively process on a subtree rooted at one of the children of node i.

• 이를 정리하면 T(n) <= T(2n/3) + Theta(1) 인 것.
  그러므로 부등식임에 따라 T(n) = O(lgn)이다.