#heap-sort

Towards the end a C++ implementation of heap and heap sort is presented.

A heap is a nearly complete binary tree. The tree is complete at every level except possibly at the lowest.

There are two kinds of heaps, max-heap and min-heap. A max-heap shall satisfy the property that $A[parent(i)] \ge A[i]$ and vice-verse for min-heap.

One can implement heaps using Array data structure. Where the left child of an index $i$ is given by $2i$ and the right child is given by the index $2i+1$.

The Heap-Sort consists of three main procedures

Heapify Runs in $\mathcal{O}(\log(n))$ time.

Build-heap which runs in linear time

Heap-sort which runs in $\mathcal{O}(n\log(n)) time$.

Pro tip: While implementing heap-sort using arrays, avoid using the zeroth index of an array.

Solutions

(CLRS, Introduction to Algorithms, 3rd ed)

$6.1-1$ Minimum = $2^{h-1}$ and maximum = $ 2^{h}-1 $

$6.1-2$ From the above relation, see that $h-1 \le \lfloor \lg n \rfloor < h$

$6.1-3$ Use induction.

$6.1-4$ The last leaf.

$6.1-5$ Yes.

$6.1-6$ No, the max-heap property is violated at node with element $14$.

$6.1-7$ Observe that those elements's left and right nodes will not belong to the array, and therefore they are leafs. It is also easy to see that any other element cannot be the leaf.

$6.2-1$ Illustration.

$6.2-2$ Code.

$6.2-3$ No effect.

$6.2-4$ Code.

$6.2-5$ Consider the case of a max-heap for a array sorted in ascending order, the heapify procedure on the root is going to take excatly $\lg n$ steps!

$6.3-1$ Illustration

$6.3-2$ The Max-Heapify procedure is designed under the assumption that if max-heapfify(A,i) is called, then the left and the right sub-heap is well-sorted and the only violation (if any) shall happen at the node only. Given this information, starting from top to bottom makes sense!

$6.3-3$ Use induction.

(ir)Relevent information

How to determine the size of an array in C. Careful with the sizeof operator and avoid a mistake that I once did. The answers, especially the second one emphasizes an important idea.