2. Start with an empty heap, and enter ten items with priorities i through 10. D
ID: 3571801 • Letter: 2
Question
2. Start with an empty heap, and enter ten items with priorities i through 10. Draw the resulting heap now remove three entries from the heap that you created in the above exercise. Draw the resulting heap Problem.
Needs these requirements for this lab
a) Create a HeapPriorityQueue interface with the following abstract methods: isEmpty, isFull, enqueue, dequeue, reheapifyupward, reheapifyDownward, reposition.
b) Create the HeapPriority Queue class. Have heapArray hold maxSize of 250 entries. Also, include the methods: default constructor, toString.
c) Create HeapoverflowException and HeapunderflowException classes
d) Create a HeapDemo class that creates a ueue object and insert the values 1-10 into the heap. Print out the heap and remove two values from the heap. Print the resulting heap. Try and show the resulting tree with the nodes on their appropriate levels along with their branches.
Explanation / Answer
In priority queus the insertion and removal of the elements depend on the priority of the given elements. Elements having higher priority are kept at the front end and with lowest priority are kept at the back end of thwe queue. E.g.: If we have an array {4,8,1,7,3,2,6,5,9,11} and we have to insert them nto an MAX priority queue, so the steps will be as under:
a) Insert 4 into an empty queue
b) As the nest element 8 is greater than 4 so it will be inserted at the front of queue or before element 4
c) Now the element 1 is minimum among 4 and 8 so it will go at the back end of queue
d) 7, which is greater than 4 and less than 8, so it will be inserted in between both
e) Now 3 will be inserted before 1, as it is greater than 1 and less than 4
in the same way the MAX priority queue will be implemented as following diagram:
The steps will be as:
4
8 4
8 4 1
8 7 4 1
8 7 4 3 1
8 7 4 3 2 1
8 7 6 4 3 2 1
8 7 6 5 4 3 2 1
9 8 7 6 5 4 3 2 1
11 9 8 7 6 5 4 3 2 1
On the basis of the implementation, a priority can be minimum or maximum type
Lab Exercise:
1) Heap Interface:
private reposition()
//to reshuffle the position
b) Constructor for the Heap class
toString Method:
c) The Heap Overflow and Underflow exception classes implementation:
d) Printing a Heap:
private int[] heap;
// to remove the two minimum value elements:
// Create object of Heap class say h
Heap h=new h();
//where deleteMin() is
//Heapify Down is
Let the five elements of the tree are {6,3,7,1,9} then tree will be
Min Heap
1
3 6
7
9
Removing 1 from this and applying Reheapify procedure the resulting tree will be
3
6
7
9
2) Again after removal of minimum element 3 it will become as:
6
7
9
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.