Heapsort
6.1 Heaps
Heap Introduction
- sorts \(n\) elements in \(O(nlog(n))\)
- in place ps. in place : only used \(O(1)\) additional memory to store data
- heat property: \[\mbox{Parent[PARENT(i)] } \leq \mbox{ A[i]}\]
Exercise
6.1-1
min: \(2 ^ h\)
max: \(2 ^ h - 1\)
6.1-2
Mathematical Induction
6.1-3
Trivial
6.1-4
Leaf
6.1-5
Yes, it is
6.1-6
No, \(6 < 7\)
6.1-7
Proof: \[ \begin{eqnarray} & & k \mbox{-th element is a leaf iff } 2k > n \newline &\Rightarrow& k \geq \lfloor n/2 \rfloor + 1 \end{eqnarray} \]
6.2 Maintaining the heap property
MaxHeapify(A,i) convert a heap that the subtree rooted at \(2 i\) and
\(2 i + 1\) are max-heaps, but \(A[i]\) might be smaller than one of its
child, thus violating the max-heap property.
The idea is to float-down \(A[i]\).
Exercise
6.2-6
Give a special case such as root 0 and node 1.
6.3 Building a heap
Do MaxHeapify(A,i) from the leaf to the root.
- Initial: leaf is a valid subtree with heap property
- Maintain: for each step of heapify, heap property is maintained
- Termination:
Exercise
6.3-2
Because MaxHeapify(A,i) needs left(i) and right(i) are subtree
with heap property.
6.4 The heapsort algorithm
My own implementation
{% include_code Heap.hpp lang:cpp cormen/data_structure/Heap.hpp %} {% include_code HeapSort.hpp lang:cpp cormen/sorting/HeapSort.hpp %}
Reference
See my github repository: cormen for details of the code.