Post date: Mar 28, 2019 4:53:8 AM
Lab 9 – Binary Heap
Objectives:
Learn How to Implement and Use Binary Heaps (Min Heap and Max Heap)
Examples:
The given class, MinHeap implements a generic Min Heap as a priority queue (with enqueue, dequeue and findFront methods). It also implements methods for building a Min Heap using both Top-Down and Bottom-Up methods.
The class TestIntegerMinHeap shows how to use the MinHeap class using Integer values
The Association class is a Comparable class that takes a pair of objects, Key (which is Comparable) and Value (which can be any object) and wrapped them into a single Comparable object.
The class, PrioritizeCities, shows how MinHeap can be used as a priority queue. It takes a set of Saudi Cities and prioritize them based on their population size with the help of the Association class.
The class HeapPrinter prints a heap of integers graphically as a tree. Note: You only need to know how to use this class and not how it is implemented.
Tasks:
(a) Manually build a Min-Heap with the keys: [11, 8, 7, 4, 9, 6, 2] using each of the following methods:
Top-Down:
Bottom-Up
(b) Run TestIntegerMinHeap to verify your solution.
(a) Heap sort is an efficient sorting method that sorts elements in an array using MinHeap. First it uses the array to create a heap (using bottom-up method), then it repeatedly dequeue min values from the MinHeap and place them back into the array starting from index 0. Update MinHeap class to include a method:
public void heapSort(T[] array)
that performs heap-sort as described above.
(b) Write a method, public void decreaseKey(int i, T key) in the MinHeap class that replaces the value at index i with the given (smaller) key and restores the heap property. Note, you must check that index i is valid and that key is indeed smaller than the value being replaced. If either of this is false, ignore the operation (i.e. do nothing). Update the TestIntegerMinHeap to test the above methods.
The file, Students.txt contains data records of 21 students, consisting of their IDs, GPAs and Names in this order. Write a program that uses the heapSort method you developed in Task 2 above to sort and print the students based on their GPA.
Note: Since ID number is the ordering field for the student class, you need to use the Association class to change the ordering field to GPA.
(a) Implement MaxHeap and TestIntegerMaxHeap similar to the given MinHeap classes in (1) above.
(b) Repeat task (2) for MaxHeap, replacing the decreaseKey method with : public void increaseKey(int i, T key) that works in a similar manner.