Priority queue

The priority queue is a data structure with each element has a priority associated with it. The high priority element served before low priority element.

Priority queues provide extra flexibility over sorting mechanism. Write a program to implement the priority queue.

source Code

package com.dsacode.Algorithm.sorting;
 
import java.util.Arrays;
 
public class PriorityQueue {
 
    private Integer[] mArray;
     
    private int mHeapSize;
     
    public PriorityQueue(int maxSize) {
        mArray = new Integer[maxSize];
        mHeapSize = 0;
    }
     
    int parentIndex(int i) {
        return (i + 1) / 2 - 1;
    }
     
    int leftChildIndex(int i) {
        return 2 * i + 1;
    }
     
    int rightChildIndex(int i) {
        return 2 * i + 2;
    }
     
 
    void maxHeapify(int i) {
        int leftChildIndex = leftChildIndex(i);
        int rightChildIndex = rightChildIndex(i);
        int largestElementIndex;
        if (leftChildIndex < mHeapSize && mArray[leftChildIndex] > mArray[i]) {
            largestElementIndex = leftChildIndex;
        } else {
            largestElementIndex = i;
        }
        if (rightChildIndex < mHeapSize && mArray[rightChildIndex] > mArray[largestElementIndex]) {
            largestElementIndex = rightChildIndex;
        }
        if (largestElementIndex != i) {
            int tmpValue = mArray[i];
            mArray[i] = mArray[largestElementIndex];
            mArray[largestElementIndex] = tmpValue;
            maxHeapify(largestElementIndex);
        }
    }
     
    void buildMaxHeap() {
        int heapSize = mArray.length;
        for (int i = heapSize / 2; i >= 0; i--) {
            maxHeapify(i);
        }
    }  
     
    public int max() {
        return mArray[0];
    }
     
    public int extractMax() {
        int max = mArray[0];
        mArray[0] = mArray[mHeapSize - 1];
        mArray[mHeapSize - 1] = null;
        mHeapSize--;
        maxHeapify(0);
        return max;
    }
     
    void increaseKey(int i, int newValue) throws Exception {
        if (newValue < mArray[i]) {
            throw new Exception("New value is smaller than current value");
        }
        mArray[i] = newValue;
        while (i > 0 && mArray[parentIndex(i)] < mArray[i]) {
            int tmpValue = mArray[parentIndex(i)];
            mArray[parentIndex(i)] = mArray[i];
            mArray[i] = tmpValue;
            i = parentIndex(i);
        }      
    }
     
    public boolean insert(int value) {
        if (mHeapSize < mArray.length) {
            mHeapSize++;
            mArray[mHeapSize - 1] = value;
            try {
                increaseKey(mHeapSize - 1, value);
            } catch (Exception e) {
                return false;
            }
            return true;
        } else {
            return false;
        }
    }
     
    public int size() {
        return mHeapSize;
    }
     
    public String toString() {
        String string = "";
        for (int i = 0; i < mHeapSize; i++) {
            string += mArray[i] + " ";
        }
        return string;
    }
     
    public static void main(String[] args) {
        int[] arr={12,34,56,23,45,78,46};
        System.out.println("unsorted array before sorting from Array : " + Arrays.toString(arr));
             
        PriorityQueue heap = new PriorityQueue(100);
        for (int i : arr) {
            heap.insert(i);
        }
         
        System.out.println("unsorted array before sorting from Heap : " +heap.toString());
         
        int heapSize = heap.size();
        System.out.print("Sorted array after sorting from PriorityQueue : ");
        for (int i = 0; i < heapSize; i++) {
            System.out.print(heap.extractMax() + " ");
        }
    }
 
}

Output

Unsorted array before sorting from Array: [12, 34, 56, 23, 45, 78, 46]
Unsorted array before sorting from Heap: 78 45 56 12 23 34 46
Sorted array after sorting from Priority Queue: 78 56 46 45 34 23 12

Algorithm Explanation

	Insert operation inserts an item into the priority queues based on the priority.
	Remove operation remove and return an item from the queue. The item removed with the highest priority.
	The MaxHeapify function takes an array A and its index i. It assumes, the left and right subtrees are already sorted.
	The procedure lets the value of A[i] float down in the max-heap so that the subtree rooted at index i becomes a max-heap.

Time Complexity

Reference

1. http://en.wikipedia.org/wiki/Priority_queue
2. http://pages.cs.wisc.edu/~vernon/cs367/notes/11.PRIORITY-Q.html