home page - news - syllabus - schedule - assignments - tutorials - tests - java - references - Mike Jacobson |
Tutorial 1 - Tutorial 2 - Tutorial 3 - Tutorial 4 - Tutorial 5 - Tutorial 6 - Tutorial 7 - Tutorial 8 - Tutorial 9 - Tutorial 10 - Tutorial 11 - Tutorial 12 - Tutorial 13 - Tutorial 14 - Tutorial 15 - Tutorial 16 - Tutorial 17 - Tutorial 18 - Tutorial 19 - Tutorial 20 - Tutorial 21 - Tutorial 22 - Tutorial 23 |
Binary Heaps and Their Applications |
The objectives of this exercise
to ensure that you understand the structure of a binary heap and its implementation using an array
to ensure that you understand operations on binary heaps well enough to be able to describe their overall structure, give pseudocode for them, and trace their execution by hand on small examples
to ensure that you understand the HeapSort algorithm well enough to describe it (using operations on binary heaps), trace its execution by hand on small examples, and state its worst-case running time
to ensure that you are familiar with the priority queue abstract data type, understand its importance, how it can be implemented using a binary heap, and how this is supported in Java.
Students should read through and try to solve the problems on this exercise before attending the tutorial.
This is based on material provided in lectures that introduce binary heaps, present algorithms for operations on binary heaps, and present their applications.
It is to be expected that all of the questions in this first section can be answered by any student who has successfully completed the prerequisites for this course, and attended the lectures in which binary heaps were discussed (reviewing the online notes, as needed).
These warmup problems will not be discussed in the tutorial; students who do have difficulty with them should contact the course instructor to get extra help.
Describe each of the following properties of a binary heap.
Give an array of length 10 that represents the following heap.
Draw the heap that is represented by the following array A, assuming that heap-size(A)=6.
Use English or pseudocode to describe algorithms to do each of the following.
State the number of operations used by each operation in the worst case, as a function of the size of the heap. You may use asymptotic notation to give your answer.
Use English or pseudocode to describe the HeapSort algorithm, using algorithms to solve the problems mentioned in the previous question as subroutines. Then trace the execution of this algorithm to sort the following array.
At this point in the course you know about two different sorting algorithms that use Θ(n log n) time to sort an array of length n in the worst case — MergeSort and HeapSort. It was suggested in class that, due to its simplicity, MergeSort might be faster (perhaps by a small constant factor) and might be easier to implement.
Describe an advantage that HeapSort has over MergeSort.
Define a priority queue, say what operations it supports, and explain how a priority queue can be implemented using a binary heap.
Consider the PriorityQueue<E> class that is currently provided as part of Java Collections framework.
Compare (and contrast) the methods provided by this Java class to the operations on priority queues that were described in class. How would you implement the kind of “priority queue” described in class using Java’s PriorityQueue class?
In this question you will show that it is possible to perform the first half of the HeapSort algorithm much more quickly — an arbitrary array (of elements of some ordered type) can be turned into a Max-Heap using time that is only linear in the length of the array.
Consider a “Heapify” operation on an array, that takes an index i (greater than or equal to 0 and less than the length of the array) as input, and that rerranges the elements of the subtree with root at position i, in the binary tree represented by this array, so that this subtree has Max-Heap order. The elements of the array that are not in this subtree should not be moved.
For example, if an array (and the binary tree) is as follows,
and heapify(1) is performed using this array, then the resulting array (and binary tree) should be produced.
Consider a recursive implementation of this, so that we start to perform the operation heapify(i) by performing the operations heapify(i.left) and heapify(i.right).
For example, we would begin to carry out the operation heapify(0) by performing the operations heapify(1) and heapify(2), which would result in the following array (and binary tree).
Describe how you could finish this — in this case, turning the entire structure that looks the the following heap,
using a number of steps that is at most logarithmic in the size of the subtree with root i.
Using the above, give (reasonably complete) pseudocode for the heapify operation that has now been informally described.
Let T(m) be the number of steps used by this method in the worst case, where m is the size of the subtree whose root is the input for heapify. Let mL and mR the the sizes of the left and right subtrees of this subtree.
Using the above information, show that if m ≥ 2 then T(m) satisfies the following inequality:
T(m) ≤ T(mL) + T(mR) + c log m
for some positive constant c.
Use the above to prove that T(m) ∈ O(m).
Hint: It will be helpful to try to show that, for sufficiently large m,
T(m) ≤ c1 m − c2 log m
for positive constants c1 and c2. The fact that the second term is being subtracted away will actually make the proof easier, here!
Now, use the above to describe another, faster, version of HeapSort. This will still use cn log n steps to sort an array of length n in the worst case, for sufficiently large n and a positive constant c, but the value of the multiplicative constant c will be reduced.
Finally, show that the new algorithm still uses Ω(n log n) steps in the worst case — while the new algorithm really is faster (when its input is large) its cost has not been improved by more than a constant factor.
Last updated:
http://www.cpsc.ucalgary.ca/~jacobs/Courses/cpsc331/W12/tutorials/tutorial17.html |