Heap

Heap Sort Theory

1. For a tree of height h, we know a binary tree is h = lg n-1 so 2^h = n-1. For a height h, the smallest number of elements possible is that 1 element is in the last level of the tree. So this algorithm is 2^(h) number of elements. For a maximum number of elements, the tree will be full and balanced, so the number of elements will be 2^(h+1) – 1. For a example a tree with height 2, will have 2^(2) nodes or 4 nodes. In the max case the tree will be full and we will have 2^3 -1 or 7 nodes. (Use the tree in answer 3 to see how it looks and count the nodes)

2. The smallest number must be a leaf node, it necessarily doesn’t have to be in the last level of a height h, or necessarily be the last node in the tree. But since the largest number is a parent and its children can’t be larger than its parent thus smallest number is a leaf node.

3. To check this we need to first use a small array then consider it at n. So for a 7 element array which is reverse sorted, the heap tree is
[pic]
Which is in fact a heap, for n numbers which is in the array of , we will find out that this tree is indeed a heap as well, since no node underneath the parents will be greater than the parent.

4. is in array form, in a tree form we can determine if this is indeed a heap. [pic]
From looking at the tree, this array is not a heap. The reason involves the left most sub tree. In order for something to be a heap the parents value must be higher or equal to all of its children. For a example 23 is larger than 17 or 14, so that would satisfy a heap. But in the bottom sub tree the parent 6 has 2 values 5 and 7, but 7 is larger than 6, so it isn’t a heap.

5. Heapify (A, 3) on the array A =

[pic]
[pic]
The function calls heapify(A,3), which switches 3 and 10, but now node 6 still violates the heapify, so it calls heapify (A,6). This switches the value of 3 and 9. Now the array is heapified.

6. For heap sort it doesn’t matter if it’s sorted in what