Heaps.
In this problem I want you to work on heaps,
and all the accompanying concepts.
See heaps (at the
end of this page are links to illustrations of
various heap operations, using the same data as in your book).
[Text, pages 151-162.] Following your text, we ignore the
0th element of arrays in Java and in C when working with heaps,
or else we use this 0th element to hold the heapsize value.
[In each case below, you must
show your work and
give reasons
for your answers. For example, in question ( i ) below,
why do you think your answer is correct?]
Suppose we used the zero element of our arrays, rather
than ignoring it or using it to hold heapsize.
Give new Parent, Left and Right
functions that would work in case we were using
A[0] as the root element of the heap.
[But we are not using this zero element in everything
below,except perhaps to hold heapsize.]
Text, Exercise 6.1-4 on page 154. [Where in a max-heap
might the smallest element reside, assuming that all elements
are distinct?]
Text, Exercise 6.1-5 on page 154. [Is an array that is
in sorted order always a min-heap?] Also is an array that is
in reverse sorted order (elements non-increasing) always
a max-heap?
Text, Exercise 6.1-6 on page 154. [Is the array with values
{23,17,14,6,13,10,1,5,7,12} a max-heap?
If not, why not? Note that these numbers are in array locations
A[1], A[2], ... A[10].]
Text, Exercise 6.2-1 on page 156. [Illustrate the operation
of Max-Heapify(A,3) on the array A =
{27,17,3,16,13,10,1,5,7,12,4,8,9,0}.] Is the result
a max-heap? If not, why not?
Text, Exercise 6.2-3 on page 156. [What is the result
of calling Max-Heapify(A,i) when the element
A[i] is larger than its children?]
Text, Exercise 6.2-4 on page 156. [What is the effect
of calling Max-Heapify(A,i) for
i > A.heap-size / 2 ?
Text, Exercise 6.2-5 on page 156. [Rewrite the code
for Max-Heapify so that it uses an iterative control
structure (a loop) instead of recursion. This is an
example of removing tail-recursion.] Hint: It's mostly just a
matter of giving the second parameter a new value while
you go around a loop again.
Suppose numbers {26, 5, 77, 1, 85, 11, 59, 15, 48, 19} are
stored in array locations A[1], ..., A[10].
Build A
into a max-heap using the algorithm Build-Max-Heap
from the text [page 157]. Notice that this
starts by calling Max-Heapify(A,5) from the text [page 154].
Then proceed down from
5 to 4 to 3 to 2 to 1.
Show that the algorithm works in the case above if you start
with 6 instead of 5 and work your way to 1.
(This is trivial.)
Text, Exercise 6.3-2 on page 159.
[Show that the algorithm fails in the case above if you start
at 1 and proceed from 1 to 2, 3, 4, to
5.]
What property
does the magic node floor(A.length/2) have? (Notice
that in Java, since we have a zero element also, this
would be floor((A.length - 1)/2).)
Text, Exercise 6.4-1 on page 160. [Illustrate the operation
of heapsort on the array A = {5,13,2,25,7,17,20,8,4}.
(Here again, A[1] = 5.)]
Priority Queues: See heaps
(at the end of this page are links to illustrations of
the priority queue operations).
Text, Exercise 6.5-1 on page 164. [Illustrate the operation
of Heap-Extract-Max on the heap
A = {15,13,9,5,12,8,7,4,0,6,2,1}.]
Text, Exercise 6.5-2 on page 165. [Illustrate the operation
of Max-Heap-Insert(A, 10) on the heap
A = {15,13,9,5,12,8,7,4,0,6,2,1}.]
Text, Exercise 6.5-4 on page 165. [Why do we bother setting
the key of the inserted node to -∞
in line 2 of
Max-Heap-Insert when the next thing we do is increase its
key to the desired value?] (This "cheating" question doesn't have
a very satisfactory answer, as far as I know. But hey, maybe
you'll come up with a good answer.)
Implementation of Heapsort:
Implement heapsort in Java or C.
You must use the algorithms as given in the text and on
our web pages. Make the code as simple as possible.
This includes storing the heapsize in the element
A[0].
As a use for your implementation, add code
to count the number of interchanges during the sort.
Using an array of size n, create an array in sorted
order (just insert i into A[i]) and count in this case.
Similarly, use an array in reverse sorted order
(just insert n-i+1 into A[i]). Finally try an
array with random data.
Use something like n=1000, or n=10000 for a run.
[If you use an "exchange" function for interchanges, it is
easier to do the count.]
In all of my runs to solve ( ii ) above, my program
shows reverse sorted order requiring the fewest interchanges
of the three possibilities above. Can you think of a reason
for this?
Revision date:2012-09-28.
(Please use ISO
8601, the International Standard.)
