Data Structures and Algorithms Highly Recommended Java Selected Tutorials

Java LinkedList-based Priority Queue Tutorial

August 25, 2023
codinghelpline

Introduction

A Priority Queue is an abstract data structure that is open on both ends. This is a special type of Queue where data elements are arranged in order of their Priority. The Priority Queue Data Structure doesn’t conform to the standard Queue pattern of FIFO (First in First Out) because it serves the elements on the basis of their priority. Each Element in the Priority Queue has a state called Priority that is used to manage the Queue in order of this feature. One end is used to insert or enqueue an element while the other is used to remove or dequeue the element. The Priority Queue elements are served on the basis of their Priority in the order of higher or lower priority based on the requirements of the application. Queue is a famous Linear Data Structure that is used in a variety of applications. It is mainly used to manage Data Flow and Tasks within an application. It is also used in Event-Driven simulations, priority tasks, and route scheduling. It is also used in Load Balancing and interrupt handling routines.

Video Tutorial – Linked List Based Priority Queue

Implementation

There are various techniques to implement a Queue such as Linked List-based, array-based, heap-based, and BinarySearchTree-based queue implementation. In either implementation, the element must have a priority associated with it so that the queue can arranged or the order of the elements according to their priority. The array-based and heap-based queue implementation can be done using fixed or dynamic arrays that can grow their size if more memory is required by the application. The LinkedList-based and BinarySearchTree-based implementation of Priority Queue always uses dynamic memory allocation which is why memory size doesn’t matter as long as the Operating System allows it to grow.

Example

(Tasks with Priority)
Create Priority Queue : Queue is Empty
Enqueue: (Task1 1)
Queue is: [(Task1 1)]
Enqueue: (Task2 5)
Queue is: []
Enqueue: (Task3 4)
Queue is: [(Task1 1), (Task3, 4), (Task2 5)]
Enqueue: (Task4 9)
Queue is: [(Task1 1), (Task3, 4), (Task2 5), (Task4 9)]
Enqueue: (Task5 2)
Queue is: [(Task1 1), (Task5 2), (Task3, 4), (Task2 5), (Task4 9)]
Dequeue:
Queue is: [(Task1 1), (Task5 2), (Task3, 4)]
Dequeue:
Queue is: [(Task1 1), (Task5 2)]

NOTE: All elements are arranged in order of their Priority - Ascending Order
and removed element from the end.

Queue Time Complexity

  • Enqueue: Array-Based O(1) Best, Average, and Worst Case as we insert at the end of the array. LinkedList-based O(N) Worst or Average Case. It is O(1) if we use a Tail reference or the list is empty. Binary Heap or Binary Search Tree the runtime is O(Log N) in the Worst and Average case. It is O(1) if the Heap or Binary Tree is empty.
  • Dequeue: Array-Based Implementation is O(N) in average and worst cases. O(1) in case there is only 1 element in the queue. In Linked-List-based implementation, it is O(1) in all best, average, and worst cases. For Heap and Binary Tree Implementation, the runtime is O(Log N) for average and worst cases. It is O(1) if there is only 1 element in the queue.
  • Peek: In Array, LinkedList, and Heap Implementations it is O(1) in all cases. In Binary Search Tree it has the complexity of O(log N) in average and worst case. It is O(1) if there is only 1 element in the Binary Search Tree.
  • Space complexity is O(N) where N is the number of elements stored in the Queue. The memory is dynamically allocated in the Linked list, Heap, and Binary Search Tree Implementations. The Array-based implementation can use fixed or dynamic arrays.

Event.java

/**
 * The <code>Task</code> class represents an Event having a Priority. The class
 * encapsulates Event name and Priority as its fields.
 *
 * @author CodingHelpLine
 * Web: https://codinghelpline.org
 */
public class Event {

    // Name of event
    private String eventName;
   
    // Priority of the Event.
    private int priority;
   
   
    /**
     * Default Constructor to initialize the Objects of Task class with
     * default values.
     *
     * @param eventName name of event
     * @param priority of the event.
     */
    public Event(String eventName, int priority) {
        this.eventName = eventName;
        this.priority = priority;
    }

    public String getEventName() {
        return eventName;
    }

    public void setEventName(String eventName) {
        this.eventName = eventName;
    }

    public int getPriority() {
        return priority;
    }

    public void setPriority(int priority) {
        this.priority = priority;
    }
   
    @Override
    /**
     * Return the String representation.
     */
    public String toString() {
        return String.format("(%s, %d)", eventName, priority);
    }
}

Node.java

/**
 * The <code>Node</code> class will represent the Link between the nodes of the
 * Priority Queue that based on linked list.
 *
 * @author CodingHelpLine
 * Web: https://codinghelpline.org
 */
public class Node {

    // Store event here
    private Event event;
   
    // Next Pointer of the node
    private Node next;
   
    /**
     * Default Constructor to initialize the Objects of Node class with
     * default values.
     *
     * @param event to store
     */
    public Node(Event event) {
        this.event  = event;
        this.next = null;
    }

    public Event getEvent() {
        return event;
    }

    public void setEvent(Event event) {
        this.event = event;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}

PriorityQueue.java

/**
 * The <code>PriorityQueue</code> class implement the Linked List Based Priority
 * Queue Data Structures that maintains the Order of Elements on the basis of
 * their priority in Ascending order.
 *
 * To Handle lower priority or higher priority variation of Priority Queue
 * Data Structure we can modify the Dequeue methods to remove from front or
 * back of the Queue.
 *
 * @author CodingHelpLine
 * Web: https://codinghelpline.org
 */
public class PriorityQueue {
   
    // Front of the Queue
    private Node front;
   
    // element counter
    private int count;

    /**
     * Default Constructor to initialize the Objects of PriorityQueue class with
     * default values.
     */
    public PriorityQueue() {
        front = null;
        count = 0;
    }
   
    /**
     * Function to insert or enqueue new element of Event into the Priority Queue.
     *
     * 1. Maintain the Order of events according to their priority.
     *
     * // Strategies
     * 1. Ascending order -> we remove from the end
     * 2. Descending order - > we remove from the front.
     *
     * @param event to store
     * @return true if added.
     */
    public boolean enqueue(Event event) {
       
        // Create node to insert
        Node node = new Node(event);
       
        // Now if the priority queue is empty
        if(this.isEmpty() || front.getEvent().getPriority() > event.getPriority()) {
           
            // Handle both cases
            // 1 - priority queue is empty
            // 2 = new event priority is less than event stored at front of PQ
            node.setNext(front);  // in case of empty
            front = node;
            count++;
            return true;
        }
       
        // find the location to insert new event
        Node current = front;
       
        // navigate to find the approriate location
        while(current.getNext() != null && current.getNext().getEvent().getPriority() < event.getPriority()) {
            current = current.getNext();
        }
       
        // Situation
        // 1 We are the end of the Priority Queue
        if(current.getNext() == null) {
            current.setNext(node);
        } else {
            // update the next reference of new node to the
            // next node of the current node.
            node.setNext(current.getNext());
           
            // update next pointer or reference of current node to point to
            // new node
            current.setNext(node);
        }
       
        count++;
        return true;
    }
   
    /**
     * Dequeue the Last Event from the Priority Queue -> Highest Priority
     * Event because we are maintaining the event in Ascending order of
     * priority.
     *
     * @return highest priority event
     */
    public Event dequeue() {
       
        // if the priority queue is empty
        if(this.isEmpty()) {
            System.out.println("This Priority Queue is empty");
            return null;
        }
        Event event = null;
       
        if(front.getNext() == null) {
            event = front.getEvent();
            front = front.getNext();
            count--;
            return event;
        }
       
        // use two references
        Node current = front, pre = null;
       
        // this way we reach the end of Priority Queue. O(N)
        while(current != null) {
           
            if(current.getNext() == null) {
                pre.setNext(current.getNext());
            }
           
            pre = current;
            current = current.getNext();
        }
       
               
        event = pre.getEvent();
        pre.setNext(null);
        count--;
       
        return event;
    }
   
    /**
     * To peek on the highest priority event.
     *
     * @return highest priority event
     */
    public Event peek() {
        // use Single pointer
        Node current = front;
        Event event = null;
       
        // this way we reach the end of Priority Queue. O(N)
        while(current != null) {
           
            // improve performance
            if(current.getNext() == null) {
                event = current.getEvent();
            }
           
            current = current.getNext();
        }
       
        return event;
    }
   
    /**
     * Size of the Priority Queue.
     *
     * @return number of elements.  
     */
    public int size() {
        return count;
    }
   
    /**
     * Print the Priority Queue.
     */
    public void print() {
       
        // if empty, notigy
        if(this.isEmpty()) {
            System.out.println("This Priority Queue is empty");
            return;
        }
       
        Node current = front;
       
        System.out.printf("[%s", current.getEvent().toString());
       
        current = current.getNext();
       
        // loop for rest of elements
        while(current != null) {
            System.out.printf(", %s", current.getEvent());
            current = current.getNext();
        }
       
        System.out.println("]");
    }
   
    /**
     * Function to check that this priority queue is empty.
     *
     * @return indicate queue is empty or not
     */
    public boolean isEmpty() {
        return front == null;
    }
}

LinkedListPriorityQueueTest.java

/**
 * The <code>LinkedListPriorityQueueTest</code> is a Main class that tests the
 * functionality of Linked List Based priority Queue Data Structure.
 *  
 * @author CodingHelpLine
 * Web: https://codinghelpline.org
 */
public class LinkedListPriorityQueueTest {

    /**
     * Main Method - Entry Point of the Program.
     *
     * @param args the command line arguments
     */
    public static void main(String[] args) {
       
        // Create PQ object
        PriorityQueue pq = new PriorityQueue();
       
        // Create some events
        Event e1 = new Event("Event1", 7);
        Event e2 = new Event("Event2", 3);
        Event e3 = new Event("Event3", 2);
        Event e4 = new Event("Event4", 9);
        Event e5 = new Event("Event5", 5);
       
       
        // Insert some elements
        pq.enqueue(e1);
        pq.print();
        System.out.println("Front of PQ: " + pq.peek());
        pq.enqueue(e2);
        pq.print();
        System.out.println("Front of PQ: " + pq.peek());
        pq.enqueue(e3);
        pq.print();
        System.out.println("Front of PQ: " + pq.peek());
        pq.enqueue(e4);
        pq.print();
        System.out.println("Front of PQ: " + pq.peek());
        pq.enqueue(e5);
        pq.print();
        System.out.println("Front of PQ: " + pq.peek());
       
        // Dequeue
        while(!pq.isEmpty()) {
            System.out.println("Front of PQ Removed: " + pq.dequeue()); // 9, 7, 5, 3, 2
            pq.print();
        }
    }

}
Views: 49

Leave a Reply

Your email address will not be published. Required fields are marked *