A Max Heap data structure is a complete binary tree, implemented using an array

Question

A Max Heap data structure is a complete binary tree, implemented using an array, where the value of a parent node is always larger than (or equal to) the values of its child nodes. It can be used for instance to implement priority queues with efficient enqueue/dequeue operations.

Enqueue i.e., inserting a new item into the max heap, works as follows:

- add the new item/node at the end of the heap array(as last item/node of the array);

- set node to last node;

- while the node's value is larger than the parent's value:

        - swap the values;

        - go to parent;

- increase heap size by 1;

Dequeue i.e., removing the root item from the max heap, works as follows:

-dequeue the item at the root node;

-copy the last value in the heap array to the root;

-decrease the heap size by 1;

-set node to root;

- while the node has 1 or 2 child nodes:

       -set next-node to the child node with the largest value;

       -if the node value is smaller than the next node value;

            -swap the values;

            -go to next node

Implement a PriorityQueue ADT with its Enqueue and Dequeue operations, as described above. Make sure to use recursion in Enqueue and Dequeue operations and not loops. Test it . . .

Note: Find more explanation of max heap and Enqueue and Dequeue operations on PriorityQueue in the appendix section.

Explanation / Answer

public class PriorityQueue {
   private Job[] heap;
   private int size;
   private int maxsize;

   private static final int root = 1;

   public PriorityQueue(int maxsize) {
       this.maxsize = maxsize;
       this.size = 0;
       heap = new Job[this.maxsize + 1];
       heap[0] = new Job("UNKNOWN", Integer.MAX_VALUE);
   }

   private int parent(int pos) {
       return pos / 2;
   }

   private int leftChild(int pos) {
       return (2 * pos);
   }

   private int rightChild(int pos) {
       return (2 * pos) + 1;
   }

   private boolean isLeaf(int pos) {
       if (pos >= (size / 2) && pos <= size) {
           return true;
       }
       return false;
   }

   private void swap(int fpos, int spos) {
       Job tmp;
       tmp = heap[fpos];
       heap[fpos] = heap[spos];
       heap[spos] = tmp;
   }

   private void maxHeapify(int pos) {
       if (!isLeaf(pos)) {
           if (heap[pos].priority < heap[leftChild(pos)].priority
                   || heap[pos].priority < heap[rightChild(pos)].priority) {
               if (heap[leftChild(pos)].priority > heap[rightChild(pos)].priority) {
                   swap(pos, leftChild(pos));
                   maxHeapify(leftChild(pos));
               } else {
                   swap(pos, rightChild(pos));
                   maxHeapify(rightChild(pos));
               }
           }
       }
   }

   public void enqueue(Job job) {
       heap[++size] = job;
       int current = size;

       while (heap[current].priority > heap[parent(current)].priority) {
           swap(current, parent(current));
           current = parent(current);
       }
   }

   public Job dequeue() throws Exception {
       Job popped = heap[root];
       heap[root] = heap[size--];
       maxHeapify(root);
       return popped;
   }

   public static void main(String... arg) {
       try {
           PriorityQueue priorityQueue = new PriorityQueue(9);
           priorityQueue.enqueue(new Job("A", 5));
           priorityQueue.enqueue(new Job("B", 3));
           priorityQueue.enqueue(new Job("C", 17));
           priorityQueue.enqueue(new Job("D", 10));
           priorityQueue.enqueue(new Job("E", 84));
           priorityQueue.enqueue(new Job("F", 19));
           priorityQueue.enqueue(new Job("G", 6));
           priorityQueue.enqueue(new Job("H", 22));
           priorityQueue.enqueue(new Job("I", 9));
           System.out.println(priorityQueue.dequeue());
           System.out.println(priorityQueue.dequeue());
           System.out.println(priorityQueue.dequeue());
           System.out.println(priorityQueue.dequeue());
           System.out.println(priorityQueue.dequeue());
           System.out.println(priorityQueue.dequeue());
           System.out.println(priorityQueue.dequeue());
           System.out.println(priorityQueue.dequeue());
           System.out.println(priorityQueue.dequeue());
          
       } catch (Exception e) {
           e.printStackTrace();
       }
   }
}

Steps to compile, execute & sample output are shown in below:

$ javac PriorityQueue.java

$ java PriorityQueue

Job Name : E Priority : 84
Job Name : H Priority : 22
Job Name : F Priority : 19
Job Name : C Priority : 17
Job Name : D Priority : 10
Job Name : G Priority : 6
Job Name : I Priority : 9
Job Name : B Priority : 3
Job Name : A Priority : 5

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.