Coders Packet

Implementation of Priority Queues using Java

By Srikar Vishnu Datta Venkata A

Using Java programming language, both Minimum Priority Queue and Maximum Priority Queue were implemented (using heaps).

Introduction

Priority Queues are special type of queues in which the elements are arranged according to the priority associated with them. Priority queues follow FIFO (First in First Out), but the elements are arranged in different fashion. 

There are two types of priority queues:

1. Min - PQ: In this type, the elements enter the queue normally, but the element with least priority comes out first from the Queue.

2. Max - PQ:  Same as min -PQ instead elements with highest priority come out first.

 

Approach:

We are going to implement priority queues with the help of heaps.

A heap is a tree with some special properties: Every node in a heap should be greater than or equal/less than or equal to their children. 

 

Types of Heaps:

Min heap: The priority of a node must be less than or equal to the priority of its children.

Max heap: The priority of a node must be greater than or equal to the priority of its children.

 

Operations in Priority Queues :

1. insertIntoQ(value, priority): Inserts data with a prioriry to the priority queue. Elements are ordered based on priority given.
2. removeMin()/removeMax(): Remove and return the element with the smallest/largest priority.
3. getMin()/getMax(): Return the element with the smallest/largest priority without deleting it.

4. Heapify: Heapify is the process of creating a heap data structure from a binary tree. It is used to create a Min-Heap or a Max-Heap.

     a. upHeapify: This is the process in which the elements inserted into the heap are adjusted accordingly, for example in min heap, elements inserted into the heap are adjusted such that a min heap is created.

     b. downHeapify: This is the process in which the elements are adjusted after the removal of an element. For example, in max heap after an element is removed this process is done to make sure that the heap is still a maxHeap.

5. size: returns the size of the Queue

6. isEmpty: checks if the Queue is empty or not and returns a boolean

 

Implementation of Code:

There are 5 classes for the implementation of Priority Queue:

Intially we create an Elements class to store the element's value and priority. The element is of T type that means it can be any type but the priority is an integer.

public class Elements {
    T value;
    int priority;
    Elements(T value, int priority){
        this.value = value;
        this.priority = priority;
    }
}

Then we have 2 separate classes for min heap and max heap named as Priority_Q_MIN_HEAP.java and Priority_Q_MAX_HEAP.java and it each class has its own implementation of the following functions:

public void insertIntoQ(T value, int priority){
        
    }

private void upHeapify(){
        
    }

public T getMin()/getMax() throws Priority_Q_Exception {
     
    }

public T removeMin()/removeMax() throws Priority_Q_Exception {
        
    }

private void downHeapify() {
        
    }

 

Also we have created our own class to throw our own exception named as Priority_Q_Exception. This class extends Exception class.

public class Priority_Q_Exception extends Exception{
}

 

Now main class,

import java.util.Scanner;

public class PQ_MAIN {
    public static Scanner scanner = new Scanner(System.in);
    public static void main(String[] args) throws Priority_Q_Exception {
        Priority_Q_MIN_HEAP pq_min = new Priority_Q_MIN_HEAP<>();
        Priority_Q_MAX_HEAP pq_max = new Priority_Q_MAX_HEAP<>();
        System.out.println("Enter the input with value and priority \n" +
                "*************** ");
        for(int i=0;i<5;i++){
            System.out.println("Enter value of element: "+(i+1));
            int value = scanner.nextInt();
            System.out.println("Enter Priority of element: "+(i+1));
            int priority = scanner.nextInt();
            pq_min.insertIntoQ(value,priority);
            pq_max.insertIntoQ(value,priority);
        }
        System.out.println("Below is the output of min priority Queue");
        while (!pq_min.isEmpty()){
            System.out.println(pq_min.removeMin());
        }
        System.out.println("Below is the output of max priority Queue");
        while (!pq_max.isEmpty()){
            System.out.println(pq_max.removeMax());
        }
        System.out.println("*************** ");
    }
}

 

Few important points:

1. After every insertion into either of the Queues, upHeapify is performed and after every removal downHeapify is performed internally.

2. The code for max heap and min heap is almost same. It differs only in the part where the elements are arranged according to the property of heap. 

3. All the elements are stored in an array and operations are performed on the array in such a way that, min/max heap is always maintained ie., elements are rearranged after every insertion and removal.

4. When we perform heapfiy operations (both upHeapify and downHeapify), the elements are arranged in ascending order (in case of min -PQ) and in descending (in case of max-PQ)

 

To execute the program, run the PQ_MAIN class.

Input:

taking input

 

Output:

output

Download project

Reviews Report

Submitted by Srikar Vishnu Datta Venkata A (srikarvishnudatta)

Download packets of source code on Coders Packet