Computer Laboratory – Course pages 2014–15: Algorithms Tick Skip to content | Access key help Search Advanced search A–Z Contact us Computer Laboratory Computer Laboratory Teaching Courses 2014–15 Algorithms Workbook for tick Computer Fundamentals Digital Electronics Discrete Mathematics Foundations of Computer Science Hardware Practical Classes ML Practical Classes Object-Oriented Programming Programming in Java Registration Algorithms Operating Systems Further Java Briefing Numerical Methods Software and Interface Design Course pages 2014–15 Algorithms Tick: Implementing a Binary Max-Heap Syllabus Course materials Information for supervisors Workbook for tick Originally, this tick did not have a star variant. On request of a student this was considered and we decided to leave it for next year. However at least one star was then independently awarded by tickers. We therefore believe it is fair to allow anyone to get a star if they so wish. The criterion shall be: building the heap with a linear-time algorithm. If you have already been assessed, it is OK to go back to the tickers with a revised version to get the star. Please make sure to attend the Algorithms practicals on Thu 2015-02-19 from 2pm-4pm or 4pm-6pm in the Intel Teaching Lab, since this is the only opportunity to get assistance from the Algorithms demonstrators. This tick will be marked in the same way as those in the Programming in Java course: after passing the tests in the unit tester you should sign up for a ticking slot using the Programming in Java sign up sheets. Introduction In this workbook you will implement a binary heap (refer to pages 33-36 and 76-77 in the Algorithms handout). Despite its simplicity, a binary heap is a very fundamental data structure which is implicitly used by the heapsort algorithm. Further, binary heaps form the basis of more sophisticated data structures such as binomial heaps and Fibonacci heaps which will be covered at a later point in the Algorithms course. Outline Specifically, your task is to implement a binary max-heap. Your program MaxHeap.java should have one method for inserting an item, one method for extracting the maximum key (if the heap is non-empty) and two constructors: one for creating an empty heap, and another for creating a heap containing a given set of n items. Implementing an O(n lg n) version of this second constructor is trivial; but, if you are good at this stuff, as an optional exercise you might choose to implement an O(n) constructor instead. It's not required, but proudly show your ticker if you did. Please follow the structure and adhere to the precise identifiers in the skeleton below. The name of a heap should be any lower-case character between 'a' and 'z', and a key value should be any upper-case character between 'A' and 'Z', where 'Z' is considered to be the largest value. Note: You may have to add additional variable(s) (which ones?) to make it work. package uk.ac.cam.your-crsid.alg1;
public class MaxHeap
{
private char heapName;
MaxHeap(char name)
{
...
}
MaxHeap(char name, String str)
{
...
}
...
}
In addition to the two constructors, the class MaxHeap should also contain the two basic heap operations, one for inserting an item and another one for extracting the maximum element. First, the method for inserting an element should look as follows: void insert(char x)
{
...
}
The method for extracting the Maximum should return the special character '_' if the heap is empty, and otherwise remove and return the largest key: char getMax()
{
...
}
Obviously, you are allowed to add additional methods for implementing these operations or just for debugging. Finally, you may use the main method to exercise your code, as in the following example (your own tests will hopefully be more thorough, but here is a starting point): public static void main(String[] args)
{
char c;
MaxHeap h = new MaxHeap('h', "CAMBRIDGEALGORITHMS");
c = h.getMax();
System.out.println(c); // expect T
h.insert('Z');
h.insert('A');
c = h.getMax();
System.out.println(c); // expect Z
c = h.getMax();
System.out.println(c); // expect S
}
Submitting your program To submit your program MaxHeap.java, produce a jar file called crsid-alg1.jar with the following content (refer to page 6 of Workbook 1 from the Programming in Java course for details): META-INF/
META-INF/MANIFEST.MF
uk/ac/cam/your-crsid/alg1/MaxHeap.class
uk/ac/cam/your-crsid/alg1/MaxHeap.java
The jar file should have its entry point set to uk.ac.cam.your-crsid.alg1.MaxHeap. You should submit your jar file by emailing it as an attachment to ticks1a-java AT cl.cam.ac.uk. Once your code successfully passes the tests you should sign up and attend a ticking slot from the Programming in Java course. © 2015 Computer Laboratory, University of Cambridge Information provided by Dr Frank Stajano
