1. Introduction

A Priority Queue is an advanced data structure that stores elements based on their priority. It allows for constant-time retrieval and removal of the element with the highest priority. One of the efficient ways to implement a priority queue is by using a binary heap.

A Binary Heap is a complete binary tree, and it can be of two types:

1. Max Heap: The key present at the root node must be the greatest among the keys present at all of its children and the same property must be recursively true for all nodes in the binary tree.

2. Min Heap: The key present at the root node must be the least among the keys present at all of its children and the same property must be recursively true for all nodes.

In this post, we will implement a Priority Queue using the Max Heap.

2. Program Steps

1. Define the structure of the Max Heap.

2. Implement methods to insert an element, delete the maximum element, and to heapify a subtree.

3. Demonstrate the usage of the Priority Queue.

3. Code Program

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

    private static final int FRONT = 1;

    public PriorityQueue(int maxsize) {
        this.maxsize = maxsize;
        this.size = 0;
        heap = new int[this.maxsize + 1];
        heap[0] = 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) {
        return pos >= (size / 2) && pos <= size;
    }

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

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

    public void insert(int element) {
        if (size >= maxsize) {
            return;
        }
        heap[++size] = element;
        int current = size;

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

    public int remove() {
        int popped = heap[FRONT];
        heap[FRONT] = heap[size--];
        maxHeapify(FRONT);
        return popped;
    }

    public static void main(String[] args) {
        PriorityQueue priorityQueue = new PriorityQueue(10);
        priorityQueue.insert(3);
        priorityQueue.insert(5);
        priorityQueue.insert(9);
        priorityQueue.insert(1);
        priorityQueue.insert(8);
        System.out.println(priorityQueue.remove());  // 9
        System.out.println(priorityQueue.remove());  // 8
    }
}

Output:

9
8

4. Step By Step Explanation

1. PriorityQueue class encapsulates the structure and operations of our max heap-based priority queue.

2. Initialization is done in the constructor where the first position (index 0) of the heap array is set to Integer.MAX_VALUE. This aids in the insert operation.

3. parent, leftChild, and rightChild methods provide easy access to the respective positions in the array-based heap.

4. The swap method swaps the two elements of the heap.

5. maxHeapify ensures that the tree remains a max heap after each operation.

6. The insert method adds an element to the heap while maintaining the max heap property.

7. The remove method removes and returns the highest priority (maximum) element from the priority queue.

8. In the main method, we've demonstrated the usage of the PriorityQueue by inserting five integers and removing the two with the highest priorities. This results in the output of 9 followed by 8.