Description
I. Overview
It’s relatively rare that you have to edit the code for a heap directly, but your knowledge of how that
code works will help you understand the efficiency of any algorithm that uses a heap. For instance, if
you do not know that a linked list must start with the head pointer and make its way to a desired spot,
then you also wouldn’t know the cost of a get. This assignment focuses on interview questions that
would require using a heap. In Java, the heap is provided by java.util.PriorityQueue so please rely on
that class instead of using your own custom heap.
For a brief refresher on heap operations, please see: https://www.interviewcake.com/concept/java/heap
II. Getting used to alternative tools
All code and explanation written in this section must be in a class named AlternativeTools
We want to write a function that takes two arguments: E[] array and int n, where E is a generic type.
This function must display (using a print) up to the first n unique elements of the array. Here are two
examples:
– Array 1 5 2 7 2 1 9 1 2 1, and n = 2. The first two unique elements are 5 and 7.
– Array 9 4 5 1 5 2 9 9, and n = 3. We will only display 4 1 because there are only two unique
elements.
1) Write a solution using a nested loop and named getNestedUnique(E[] array, int n). The time
complexity should be Θ(n2
) and space complexity Θ(1) since you display as you go.
2) Write getSortedUnique, which starts by sorting and then goes through the array in a single
loop. The time complexity of sorting is Θ(n log n), then your loop is in Θ(n). Space is still Θ(1).
3) Write getMapUnique, which has two loops. The first loop uses a map to count how many
times each number appears. The second loop uses the map to display the first n unique
elements. As a comment above your code, write its time and space complexity.
4) Write getHeapUnique. Similarly to solution 3, it will operate in two loops and use a map.
However, the map here should be storing a pair: number of times each character appeared
and the index of its first appearance. Your second loop should be over the map, not the array.
Use a heap in the second loop.
“This magnificent butterfly finds a little heap of dirt and sits still on it; but man will never on his heap
of mud keep still.” – Joseph Conrad
III. Explaining and illustrating the use of a heap
Your work should be in a PDF file named TextAndImageQuestions
1) Read pages 324 to 327 on heapsort. Also see https://www.youtube.com/watch?v=2DmK_H7IdTo
In your own words, briefly explain how heap sort works.
Show the details of how you sort the following two arrays:
– [12 6 10 5 1 9}
– [1 14 7 8 3]
Yes, there are applets online that can do it step by step. So you’re expected to get the point on this
question. But if this question comes up in your final exam or next quiz, you need to know how to do it
yourself. So the most important aspect is that you learn to do this.
2) Explain whether we can turn a min-heap into a Binary Search Tree (BST) in Θ(log n).
IV. A seasonal problem
All code and explanation written in this section must be in a class named DeathComesKnocking
Consider N houses, each of whom contains Ni healthy students. Each day, an infected student visits
one of these houses to party. When a house is visited by the student, all of the students in it are
exposed to the virus and half of them get sick so they’re taken to the hospital (i.e. they would not be
in the house the next day). The problem is to find the maximum number of students that can be
exposed to the virus within a given number of days.
The function has two arguments: getInfections(int[] houses, int days). Here are some examples:
– Over 5 days, with houses initially containing [8, 2, 6, 4, 10] students, we’d infect up to 33.
– Over 3 days, with houses initially containing [5, 6] students, we’d infect up to 14.
The heap must be involved in your solution.
V. Brief summaries
Your work should be in a PDF file named Summaries
Watch the short recording (which is immediately below the link for this assignment). Then, answer
each of the following in one brief paragraph:
1) How would you find the maximum in a min heap?
2) How would you measure the extent to which a tree can efficiently be put in an array?
The short recording will give you answers, as narrated by the instructor. We are interested in hearing
your own words here. The Turn-It-In software for plagiarism check will also be used to ensure that
we’re reading your words, rather than the words of a random person on the internet.
Questions? Existential doubts? Feel free to contact our teaching assistant, Elinore at: eavensek@miamioh.edu
