DSABook – Review questions

9.5 Review questions

This final section contains some review questions about the contents of this chapter.

9.5.1 Review questions: Binary heaps

Which feature of heaps allows them to be efficienty implemented using an array?

Heaps are complete binary trees
Heaps are binary trees
Heaps are binary search trees
Heaps are full binary trees

A heap is not a BST.
In general, just being a binary tree (or even a full binary tree) is not enough to let something be implemented using an array.

In a max-heap containing $n$ elements, what is the position of the element with the greatest value?

Remember this is a max-heap. So where is the biggest element?
It is at the root. So, what position holds the root?

In a max-heap containing $n$ elements, what is the position of the element with the least value?

Remember this is a max-heap. So where is the smallest element?
It has to be at the bottom.
But, it could be anywhere at the bottom.

Consider a node $R$ of a complete binary tree whose value is stored in position $i$ of an array representation for the tree. If $R$ has a left child, where will the left child’s position be in the array?

If you have a right sibling, it is at $i+1$ .
If you have a left sibling, it is at $i-1$ .
If you have a parent, it is at $\lfloor (i-1)/2 \rfloor$ .
If you have a right child, it is at $2*i+2$ .
If you have a left child, it is at $2*i+1$ .

Consider a node $R$ of a complete binary tree whose value is stored in position $i$ of an array representation for the tree. If $R$ has a left sibling, where will the left sibling’s position be in the array?

If you have a parent, it is at $\lfloor (i-1)/2 \rfloor$ .
If you have a right child, it is at $2*i+2$ .
If you have a left child, it is at $2*i+1$ .
If you have a right sibling, it is at $i+1$ .
If you have a left sibling, it is at $i-1$ .

Consider a node $R$ of a complete binary tree whose value is stored in position $i$ of an array representation for the tree. If $R$ has a parent, where will the parent’s position be in the array?

If you have a right sibling, it is at $i+1$ .
If you have a left sibling, it is at $i-1$ .
If you have a right child, it is at $2*i+2$ .
If you have a left child, it is at $2*i+1$ .
If you have a parent, it is at $\lfloor (i-1)/2 \rfloor$ .

Consider a node $R$ of a complete binary tree whose value is stored in position $i$ of an array representation for the tree. If $R$ has a right child, where will the right child’s position be in the array?

If you have a right sibling, it is at $i+1$ .
If you have a left sibling, it is at $i-1$ .
If you have a parent, it is at $\lfloor (i-1)/2 \rfloor$ .
If you have a left child, it is at $2*i+1$ .
If you have a right child, it is at $2*i+2$ .

Which of these is a true statement about the worst-case time for operations on heaps?

Both insertion and removal are better than linear
Insertion is better than linear, but removal is not
Removal is better than linear, but insertion is not
Neither insertion nor removal are better than linear

Insert works by putting the new element at the end of the array, and moving it up the tree as appropriate.
So its worst-case cost is proportional to the depth of the tree.
Remove works swapping the element to remove with the one at the end of the array. Then move that moved item up or down the tree, as appropriate.
So its worst-case cost is proportional to the depth of the tree.

9.5.2 Review questions: Heapsort

Answer TRUE or FALSE.

Heapsort (as the code is written in this chapter) is a stable sorting algorithm. Recall that a stable sorting algorithm maintains the relative order of records with equal keys.

True
False

What happens when two equal values are in separate branches of the tree?
Can the one appearing later in the array move up in the tree?

A disadvantage of Heapsort is:

It is not stable (i.e., records with equal keys might not remain in the same order after sorting)
It needs a lot of auxilliary storage
Its average case running time is $O(n^2)$
None of these answers

Heapsort does not need auxilliary storage.
Heapsort runs in $O(n \log n)$ time.
Equal-valued records might be in different sides of the heap, and can get out of relative order.

In which cases are the time complexities the same for Heapsort?

Worst and Average
Worst and Best
Best and Average
Worst, Average and Best

Does Heapsort’s cost vary according to the order of the array input values?
No, it does not matter what order the input values have.
However, the best case occurs when all the values are same.

(Assuming no duplicate key values) The order of the input records has what impact on the number of comparisons required by Heapsort (as presented in this chapter)?

There is a constant factor difference
None
There is a big difference, the asymptotic running time can change

Can Heapsort’s behaviour change depending on outcome of a comparison?
Yes, it changes things a little bit in that it might move things up and down the heap more or less.
But this does not matter, because removing a value from the heap normally costs $\log n$ .

What is the worst-case time for Heapsort to sort an array of n records that each have unique key values?

Does Heapsort’s number of comparisons depend on the particular order of the input array?
Only a little bit, Heapsort still does basically the same work regardless of input data order.

What is the running time of Heapsort when the input is an array where all key values are equal?

Heapsort has the same asymptotic cost in the best, average, and worst cases, but only if the key values are all unique.
If you have a heap with all equal key values, what will the siftdown operation do?
In that case, siftdown will always return immediately, resulting in a constant time operation. Since Heapsort calls siftdown $n$ times, the total cost is $O(n)$ .

How much auxilliary space or overhead (beyond the array holding the records) is needed by Heapsort?

$O(1)$
$O(\log n)$
$O(n)$
$O(n^2)$

Heapsort does not require any auxilliary arrays.