Priority Queue

Priority Queue Implementation

Pinterest LinkedIn Tumblr

A priority queue is a data structure and each element has a priority associated with it. The high priority served before with low priority. The priority queue key will be unique. The priority queue can be implemented using Unordered linked list, ordered linked list, Ordered array, and balanced Binary search tree.

Write a program to implement the priority queue.

Algorithm Explanation

Insert operation inserts the data dynamically into the queue with a priority level. Delete minimum operation find the minimum element from the queue and delete.
Heap is an internal data structure for storing the priority queue elements. The priority queue uses first in first out property (FIFO) with a priority level.
Priority queue makes sure, it remove highest priority node before the lowest priority node.
maxHeapify property validates the above property. Extract maximum function extracts the maximum value from the priority queue.

Source Code

package com.dsacode.DataStructre.priorityqueue;
 
import java.util.Arrays;
 
public class PriorityQueueImpl {
    private Integer[] mArray;
    private int mHeapSize;
 
    public PriorityQueueImpl(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) {
 
        Integer[] array = { 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 };
        System.out.println("Array of items for insert Priority Queue: "
                + Arrays.toString(array));
        PriorityQueueImpl heap = new PriorityQueueImpl(100);
        for (int i : array) {
            heap.insert(i);
        }
 
        System.out.println("Items from Priority Queue: " + heap.toString());
 
        System.out
                .print("Items from Priority Queue extracted using Max items: ");
        int heapSize = heap.size();
        for (int i = 0; i < heapSize; i++) {
            System.out.print(heap.extractMax() + " ");
        }
        System.out.println();
 
    }
}

Output

Array of items for insert Priority Queue: [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]
Items from Priority Queue: 16 14 10 8 7 3 9 1 4 2
Items from Priority Queue extracted using Max items: 16 14 10 9 8 7 4 3 2 1

Source Explanation

Construct the priority queue using array length.
Insert the elements from the array to priority queue using insert operation.
Insert function inserts the value to the array and increases the key. The increase key function swaps the parent index with array element.
Print the priority queue items and iterate all the item from priority queue using extract max function and display the values.
Extract max function extracts the maximum element from the heap and heavily the heap.

Complexity

OperationsBest CaseAverage Caseworst Case
Find Min/Find MaxO(1)
InsertionO(log n)
DeletionO(log n)

Real Applications

  1. Prim’s algorithm for minimum spanning tree
  2. Huffman coding
  3. Dijkstra’s algorithm
  4. Manage the network bandwidth information
  5. Stock application
  6. Sum of powers in numerical system
  7. Spam filtering in email
  8. Load balancing
  9. Interrupt handling

Reference

  1. https://en.wikipedia.org/wiki/Priority_queue
  2. http://pages.cs.wisc.edu/~vernon/cs367/notes/11.PRIORITY-Q.html
  3. http://www.eecs.wsu.edu/~ananth/CptS223/Lectures/heaps.pdf
  4. http://www.utdallas.edu/~pervin/te3346/Heaps.pdf
  5. http://www.cs.cmu.edu/~pattis/15-1XX/15-200/lectures/collectionsii/
  6. http://visualgo.net/heap.html

Write A Comment