Priority Queue

Priority Queue is data structure that makes use of  Heap Data structure  and its properties (Max Heap & Min Heap)

Data structure for maintaining set S of elements, each element associated with a key.

As Heap, priority queue is also of 2 types
1. Max Priority Queue
2. Min Priority Queue

Max Priority Queue Implementation

import java.util.Arrays;

public class MaxPriorityQueue {

    int[] arr = null;
    int size;

    public MaxPriorityQueue() {
        this.arr = new int[10];
        size = 0;
    }

    public int maximum() throws Exception {
        if (isEmpty()) throw new Exception("Queue empty");
        return arr[0];
    }

    private boolean isEmpty() { return size() == 0; }

    private int size() { return size; }

    public int extractMaximum() throws Exception {
        int max = maximum();
        arr[0] = arr[--size];
        maxHeapify(0);
        return max;
    }

    public void insertKey(int key) throws Exception {
        arr[size++]=Integer.MIN_VALUE;
        heapIncreaseKey(key);
    }

    private void heapIncreaseKey(int key) throws Exception {
        if(arr[size-1]>key) throw new Exception("New Key is smaller than current key");
        arr[size-1]=key;
        int i=size-1;
        while(i>=0 && arr[parent(i)]<arr[i]){
            swap(parent(i),i);
            i=parent(i);
        }
    }

    private int parent(int i) { return (i-1)/2; }

    private void maxHeapify(int i) {
        int l = left(i);
        int r = right(i);
        int largest = i;
        if (l < size() && arr[l] > arr[largest])
            largest = l;
        if (r < size() && arr[r] > arr[largest])
            largest = r;
        if (largest != i) {
            swap(largest, i);
            maxHeapify(largest);
        }
    }

    private void swap(int largest, int i) {
        int temp = arr[largest];
        arr[largest] = arr[i];
        arr[i] = temp;
    }

    private int right(int i) { return 2 * i + 2; }

    private int left(int i) { return 2 * i + 1; }

    @Override    public String toString() {
        StringBuilder sb = new StringBuilder("");
        Arrays.stream(arr).forEach(j->sb.append(j +" "));
        return sb.toString();
    }
}