Heap Priority Queue Program
Description
This program uses an ArrayList to build a heap priority queue.Associated Concepts:
Heap
Priority Queue
Priority Queue
Algorithm:
QueueInterface Java interface
HeapPriorityQueue class
Client program
EmptyQueueException class
It defines a Java interface QueueInterface which includes
five abstract methods.
enQueue(), deQueue(), peek(), size(), and isEmpty().
HeapPriorityQueue class
It implements QueueInterface.
Two private data members:
Constructor:
size(), isEmpty(), enQueue(), peek(), deQueue(), and toString() methods.
size() method
isEmpty() method
void enQueue(E object) method
E peep() method
E deQueue() method
String toString() method
Two private data members:
A generic ArrayList object to store objects.
An integer variable called lastIndex which is the index of the last object.
An integer variable called lastIndex which is the index of the last object.
Constructor:
Initialize the data members:
- Create the generic ArrayList object.
- Set the lastIndex to 0.
- Create the generic ArrayList object.
- Set the lastIndex to 0.
size(), isEmpty(), enQueue(), peek(), deQueue(), and toString() methods.
size() method
Return the number of objects in the heap.
isEmpty() method
Return true if the heap is empty; false otherwise.
void enQueue(E object) method
1. Add the object as the last node in the heap.
2. Perform the up-heap bubbling until the heap properties are restored.
2. Perform the up-heap bubbling until the heap properties are restored.
E peep() method
1. Check for the empty heap.
2. Retrieve and return the object at the root.
2. Retrieve and return the object at the root.
E deQueue() method
1. Check for the empty heap.
2. Move the last node to the root.
3. Perform the down-heap bubbling until the heap properties are restored.
4. Return the removed object at the old root.
2. Move the last node to the root.
3. Perform the down-heap bubbling until the heap properties are restored.
4. Return the removed object at the old root.
String toString() method
Print the heap.
Client program
Create a HeapPriorityQueue object.
Call the methods defined in the HeapPriorityQueue class to test them.
Call the methods defined in the HeapPriorityQueue class to test them.
EmptyQueueException class
Extend the RuntimeException class.
Invoke the superclass' constructor in the constructor.
Invoke the superclass' constructor in the constructor.