What is a Priority Queue Data Structure? Implementation, Type & Many More

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

// Structure for the elements in the priority queue
struct Item {
    int value;
    int priority;
};

// Class for priority queue
class Queue {
public:
    // Store the elements of the priority queue
    vector<Item> pr;

    // Function to insert a new element into the priority queue
    void enqueue(int value, int priority) {
        Item newItem;
        newItem.value = value;
        newItem.priority = priority;
        pr.push_back(newItem);
    }

    // Function to check the top element
    int peek() {
        int highestPriority = INT_MIN;
        int ind = -1;

        // Check for the element with the highest priority
        for (int i = 0; i < pr.size(); i++) {
            if (highestPriority == pr[i].priority && ind > -1 && pr[ind].value < pr[i].value) {
                highestPriority = pr[i].priority;
                ind = i;
            } else if (highestPriority < pr[i].priority) {
                highestPriority = pr[i].priority;
                ind = i;
            }
        }

        // Return position of the element
        return ind;
    }

    // Function to remove the element with the highest priority
    void dequeue() {
        // Find the position of the element with the highest priority
        int ind = peek();

        // Remove the element at that position
        pr.erase(pr.begin() + ind);
    }

    // Main function to demonstrate the priority queue
    void main() {
        // Function Call to insert elements as per the priority
        enqueue(14, 2);
        enqueue(18, 4);
        enqueue(16, 4);
        enqueue(12, 3);

        // Stores the top element at the moment
        int ind = peek();
        cout << pr[ind].value << endl;

        // Dequeue the top element
        dequeue();

        // Check the top element
        ind = peek();
        cout << pr[ind].value << endl;

        // Dequeue the top element
        dequeue();

        // Check the top element
        ind = peek();
        cout << pr[ind].value << endl;
    }
};

// Entry point of the program
int main() {
    Queue q;
    q.main();
    return 0;
}

import java.util.*;

// Structure for the elements in the priority queue
class Item {
    public int value;
    public int priority;
}

class Queue {
    // Store the element of a priority queue
    static Item[] pr = new Item[100000];

    // Pointer to the last index
    static int size = -1;

    // Function to insert a new element into priority queue
    static void enqueue(int value, int priority) {
        // Increase the size
        size++;

        // Insert the element
        pr[size] = new Item();
        pr[size].value = value;
        pr[size].priority = priority;
    }

    // Function to check the top element
    static int peek() {
        int highestPriority = Integer.MIN_VALUE;
        int ind = -1;

        // Check for the element with highest priority
        for (int i = 0; i <= size; i++) {
            // If priority is same, choose the element with the highest value
            if (highestPriority == pr[i].priority && ind > -1 && pr[ind].value < pr[i].value) {
                highestPriority = pr[i].priority;
                ind = i;
            } else if (highestPriority < pr[i].priority) {
                highestPriority = pr[i].priority;
                ind = i;
            }
        }

        // Return position of the element
        return ind;
    }

    // Function to remove the element with the highest priority
    static void dequeue() {
        // Find the position of the element with highest priority
        int ind = peek();

        if (ind != -1) {
            // Shift the element one index before from the position of the element with highest priority
            for (int i = ind; i < size; i++) {
                pr[i] = pr[i + 1];
            }

            // Decrease the size of the priority queue by one
            size--;
        }
    }

    public static void main(String[] args) {
        // Function Call to insert elements as per the priority
        enqueue(14, 2);
        enqueue(18, 4);
        enqueue(16, 4);
        enqueue(12, 3);

        // Stores the top element at the moment
        int ind = peek();
        if (ind != -1) {
            System.out.println(pr[ind].value);
        }

        // Dequeue the top element
        dequeue();

        // Check the top element
        ind = peek();
        if (ind != -1) {
            System.out.println(pr[ind].value);
        }

        // Dequeue the top element
        dequeue();

        // Check the top element
        ind = peek();
        if (ind != -1) {
            System.out.println(pr[ind].value);
        }
    }
}
    

class Item {
    constructor(value, priority) {
        this.value = value;
        this.priority = priority;
    }
}

class Queue {
    constructor() {
        this.pr = [];
        this.size = -1;
    }

    enqueue(value, priority) {
        this.size++;
        this.pr[this.size] = new Item(value, priority);
    }

    peek() {
        let highestPriority = -Infinity;
        let ind = -1;

        for (let i = 0; i <= this.size; i++) {
            if (highestPriority === this.pr[i].priority) {
                if (ind > -1 && this.pr[ind].value < this.pr[i].value) {
                    highestPriority = this.pr[i].priority;
                    ind = i;
                }
            } else if (highestPriority < this.pr[i].priority) {
                highestPriority = this.pr[i].priority;
                ind = i;
            }
        }

        return ind;
    }

    dequeue() {
        const ind = this.peek();

        for (let i = ind; i < this.size; i++) {
            this.pr[i] = this.pr[i + 1];
        }

        this.size--;
    }

    static main() {
        const queue = new Queue();

        queue.enqueue(14, 2);
        queue.enqueue(18, 4);
        queue.enqueue(16, 4);
        queue.enqueue(12, 3);

        let ind = queue.peek();
        console.log(queue.pr[ind].value);

        queue.dequeue();

        ind = queue.peek();
        console.log(queue.pr[ind].value);

        queue.dequeue();

        ind = queue.peek();
        console.log(queue.pr[ind].value);
    }
}

// Run the main function
Queue.main();

#include <iostream>
using namespace std;

class PriorityQueueNode {
public:
    int data;
    int priority;
    PriorityQueueNode* next;

    PriorityQueueNode(int value, int pr) {
        data = value;
        priority = pr;
        next = nullptr;
    }
};

class PriorityQueue {
private:
    PriorityQueueNode* front;

public:
    PriorityQueue() {
        front = nullptr;
    }

    bool isEmpty() {
        return front == nullptr;
    }

    void push(int value, int priority) {
        PriorityQueueNode* newNode = new PriorityQueueNode(value, priority);

        if (isEmpty() || front->priority > priority) {
            newNode->next = front;
            front = newNode;
        } else {
            PriorityQueueNode* temp = front;
            while (temp->next != nullptr && temp->next->priority <= priority) {
                temp = temp->next;
            }
            newNode->next = temp->next;
            temp->next = newNode;
        }
    }

    void pop() {
        if (isEmpty()) {
            cout << "Queue is Empty!" << endl;
        } else {
            PriorityQueueNode* temp = front;
            front = front->next;
            delete temp;
        }
    }

    int peek() {
        if (isEmpty()) {
            cout << "Queue is Empty!" << endl;
            return -1; // Return -1 if the queue is empty
        } else {
            return front->data;
        }
    }

    void traverse() {
        if (isEmpty()) {
            cout << "Queue is Empty!" << endl;
        } else {
            PriorityQueueNode* temp = front;
            while (temp != nullptr) {
                cout << temp->data << " ";
                temp = temp->next;
            }
            cout << endl;
        }
    }
};

int main() {
    PriorityQueue pq;
    pq.push(14, 1);
    pq.push(18, 2);
    pq.push(16, 3);
    pq.push(12, 0);

    pq.traverse(); // Output: 12 14 18 16

    pq.pop();      // Removes the element with the highest priority (lowest priority number)

    pq.traverse(); // Output: 14 18 16

    return 0;
}
    

using System;

class PriorityQueueNode
{
    public int Data { get; set; }
    public int Priority { get; set; }
    public PriorityQueueNode Next { get; set; }

    public PriorityQueueNode(int value, int pr)
    {
        Data = value;
        Priority = pr;
        Next = null;
    }
}

class PriorityQueue
{
    private PriorityQueueNode front;

    public PriorityQueue()
    {
        front = null;
    }

    public bool IsEmpty()
    {
        return front == null;
    }

    public void Push(int value, int priority)
    {
        PriorityQueueNode newNode = new PriorityQueueNode(value, priority);

        if (IsEmpty())
        {
            front = newNode;
        }
        else
        {
            if (front.Priority > priority)
            {
                newNode.Next = front;
                front = newNode;
            }
            else
            {
                PriorityQueueNode temp = front;
                while (temp.Next != null && temp.Next.Priority <= priority)
                {
                    temp = temp.Next;
                }
                newNode.Next = temp.Next;
                temp.Next = newNode;
            }
        }
    }

    public void Pop()
    {
        if (!IsEmpty())
        {
            front = front.Next;
        }
    }

    public int Peek()
    {
        return IsEmpty() ? -1 : front.Data;
    }

    public void Traverse()
    {
        if (IsEmpty())
        {
            Console.WriteLine("Queue is Empty!");
        }
        else
        {
            PriorityQueueNode temp = front;
            while (temp != null)
            {
                Console.Write(temp.Data + " ");
                temp = temp.Next;
            }
        }
    }
}

class Program
{
    static void Main()
    {
        PriorityQueue pq = new PriorityQueue();
        pq.Push(14, 1);
        pq.Push(18, 2);
        pq.Push(16, 3);
        pq.Push(12, 0);

        pq.Traverse(); // Output: 12 14 18 16

        pq.Pop();

        Console.WriteLine();
        pq.Traverse(); // Output after pop: 14 18 16
    }
}

class PriorityQueueNode:
    def __init__(self, value, priority):
        self.data = value
        self.priority = priority
        self.next = None

class PriorityQueue:
    def __init__(self):
        self.front = None

    def is_empty(self):
        return self.front is None

    def push(self, value, priority):
        new_node = PriorityQueueNode(value, priority)

        if self.is_empty() or self.front.priority > priority:
            new_node.next = self.front
            self.front = new_node
        else:
            temp = self.front
            while temp.next and temp.next.priority <= priority:
                temp = temp.next
            new_node.next = temp.next
            temp.next = new_node

    def pop(self):
        if self.is_empty():
            return
        else:
            self.front = self.front.next

    def peek(self):
        if self.is_empty():
            return None
        else:
            return self.front.data

    def traverse(self):
        if self.is_empty():
            return "Queue is Empty!"
        else:
            temp = self.front
            result = ''
            while temp:
                result += str(temp.data) + " "
                temp = temp.next
            return result.strip()

# Example usage
pq = PriorityQueue()
pq.push(14, 1)
pq.push(18, 2)
pq.push(16, 3)
pq.push(12, 0)

print(pq.traverse())  # Output: 12 14 18 16

pq.pop()
print(pq.traverse())  # Output: 14 18 16
    

class PriorityQueueNode {
    int data;
    int priority;
    PriorityQueueNode next;

    public PriorityQueueNode(int value, int pr) {
        this.data = value;
        this.priority = pr;
        this.next = null;
    }
}

class PriorityQueue {
    private PriorityQueueNode front;

    public PriorityQueue() {
        this.front = null;
    }

    public boolean isEmpty() {
        return front == null;
    }

    public void push(int value, int priority) {
        PriorityQueueNode newNode = new PriorityQueueNode(value, priority);

        if (isEmpty() || front.priority > priority) {
            newNode.next = front;
            front = newNode;
        } else {
            PriorityQueueNode temp = front;
            while (temp.next != null && temp.next.priority <= priority) {
                temp = temp.next;
            }
            newNode.next = temp.next;
            temp.next = newNode;
        }
    }

    public void pop() {
        if (!isEmpty()) {
            front = front.next;
        }
    }

    public int peek() {
        if (!isEmpty()) {
            return front.data;
        }
        return -1; // Return -1 if queue is empty
    }

    public void traverse() {
        if (isEmpty()) {
            System.out.println("Queue is Empty!");
        } else {
            PriorityQueueNode temp = front;
            while (temp != null) {
                System.out.print(temp.data + " ");
                temp = temp.next;
            }
            System.out.println();
        }
    }
}

public class Main {
    public static void main(String[] args) {
        PriorityQueue pq = new PriorityQueue();
        pq.push(14, 1);
        pq.push(18, 2);
        pq.push(16, 3);
        pq.push(12, 0);

        pq.traverse();

        pq.pop();
        pq.traverse();
    }
}
    

class PriorityQueueNode {
  constructor(value, priority) {
    this.data = value;
    this.priority = priority;
    this.next = null;
  }
}

class PriorityQueue {
  constructor() {
    this.front = null;
  }

  isEmpty() {
    return this.front === null;
  }

  push(value, priority) {
    const newNode = new PriorityQueueNode(value, priority);

    if (this.isEmpty() || this.front.priority > priority) {
      newNode.next = this.front;
      this.front = newNode;
    } else {
      let temp = this.front;
      while (temp.next && temp.next.priority <= priority) {
        temp = temp.next;
      }
      newNode.next = temp.next;
      temp.next = newNode;
    }
  }

  pop() {
    if (this.isEmpty()) {
      return;
    } else {
      this.front = this.front.next;
    }
  }

  peek() {
    if (this.isEmpty()) {
      return null;
    } else {
      return this.front.data;
    }
  }

  traverse() {
    if (this.isEmpty()) {
      return "Queue is Empty!";
    } else {
      let temp = this.front;
      let result = '';
      while (temp) {
        result += temp.data + " ";
        temp = temp.next;
      }
      return result.trim();
    }
  }
}

// Example usage
const pq = new PriorityQueue();
pq.push(14, 1);
pq.push(18, 2);
pq.push(16, 3);
pq.push(12, 0);

console.log(pq.traverse());  // Output: 12 14 18 16

pq.pop();
console.log(pq.traverse());  // Output: 14 18 16

#include <iostream>

class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int value) : val(value), left(nullptr), right(nullptr) {}
};

class PriorityQueueBST {
private:
    TreeNode* root;

    TreeNode* insert(TreeNode* node, int val) {
        if (!node) {
            return new TreeNode(val);
        }
        if (val < node->val) {
            node->left = insert(node->left, val);
        } else {
            node->right = insert(node->right, val);
        }
        return node;
    }

    TreeNode* findMax(TreeNode* node) {
        while (node->right) {
            node = node->right;
        }
        return node;
    }

    TreeNode* deleteNode(TreeNode* node, int val) {
        if (!node) {
            return nullptr;
        }
        if (val < node->val) {
            node->left = deleteNode(node->left, val);
        } else if (val > node->val) {
            node->right = deleteNode(node->right, val);
        } else {
            if (!node->left) {
                return node->right;
            }
            if (!node->right) {
                return node->left;
            }
            TreeNode* temp = findMax(node->left);
            node->val = temp->val;
            node->left = deleteNode(node->left, temp->val);
        }
        return node;
    }

public:
    PriorityQueueBST() : root(nullptr) {}

    void insert(int val) {
        root = insert(root, val);
    }

    int deleteMax() {
        if (!root) {
            return -1; // Assuming -1 as an indication of an empty tree.
        }
        TreeNode* maxNode = findMax(root);
        int maxVal = maxNode->val;
        root = deleteNode(root, maxVal);
        return maxVal;
    }

    bool isEmpty() {
        return root == nullptr;
    }
};

// Example usage:
int main() {
    PriorityQueueBST pq;
    pq.insert(10);
    pq.insert(20);
    pq.insert(5);
    pq.insert(15);

    while (!pq.isEmpty()) {
        std::cout << pq.deleteMax() << std::endl;
    }

    return 0;
}

using System;

class TreeNode
{
    public int Val;
    public TreeNode Left;
    public TreeNode Right;

    public TreeNode(int val)
    {
        Val = val;
        Left = null;
        Right = null;
    }
}

class PriorityQueueBST
{
    private TreeNode root;

    public PriorityQueueBST()
    {
        root = null;
    }

    public void Insert(int val)
    {
        root = InsertHelper(root, val);
    }

    private TreeNode InsertHelper(TreeNode node, int val)
    {
        if (node == null)
            return new TreeNode(val);

        if (val < node.Val)
            node.Left = InsertHelper(node.Left, val);
        else
            node.Right = InsertHelper(node.Right, val);

        return node;
    }

    public int? Delete()
    {
        if (root == null)
            return null;

        int maxVal = FindMax(root).Val;
        root = DeleteNode(root, maxVal);
        return maxVal;
    }

    private TreeNode FindMax(TreeNode node)
    {
        while (node.Right != null)
            node = node.Right;
        return node;
    }

    private TreeNode DeleteNode(TreeNode node, int val)
    {
        if (node == null)
            return null;

        if (val < node.Val)
            node.Left = DeleteNode(node.Left, val);
        else if (val > node.Val)
            node.Right = DeleteNode(node.Right, val);
        else
        {
            if (node.Left == null)
                return node.Right;
            if (node.Right == null)
                return node.Left;

            TreeNode temp = FindMax(node.Left);
            node.Val = temp.Val;
            node.Left = DeleteNode(node.Left, temp.Val);
        }

        return node;
    }

    public bool IsEmpty()
    {
        return root == null;
    }
}

// Example usage
class Program
{
    static void Main()
    {
        PriorityQueueBST pq = new PriorityQueueBST();
        pq.Insert(10);
        pq.Insert(20);
        pq.Insert(5);
        pq.Insert(15);

        while (!pq.IsEmpty())
        {
            Console.WriteLine(pq.Delete());
        }
    }
}

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

class PriorityQueueBST:
    def __init__(self):
        self.root = None

    def insert(self, val):
        def helper(node, val):
            if not node:
                return TreeNode(val)
            if val < node.val:
                node.left = helper(node.left, val)
            else:
                node.right = helper(node.right, val)
            return node

        self.root = helper(self.root, val)

    def delete(self):
        def find_max(node):
            while node.right:
                node = node.right
            return node

        def delete_node(node, val):
            if not node:
                return None
            if val < node.val:
                node.left = delete_node(node.left, val)
            elif val > node.val:
                node.right = delete_node(node.right, val)
            else:
                if not node.left:
                    return node.right
                if not node.right:
                    return node.left
                temp = find_max(node.left)
                node.val = temp.val
                node.left = delete_node(node.left, temp.val)
            return node

        if not self.root:
            return None
        max_val = find_max(self.root).val
        self.root = delete_node(self.root, max_val)
        return max_val

    def is_empty(self):
        return self.root is None

# Example usage:
pq = PriorityQueueBST()
pq.insert(10)
pq.insert(20)
pq.insert(5)
pq.insert(15)

while not pq.is_empty():
    print(pq.delete())
    

class TreeNode {
    int val;
    TreeNode left, right;

    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

class PriorityQueueBST {
    private TreeNode root;

    PriorityQueueBST() {
        this.root = null;
    }

    public void insert(int val) {
        this.root = insertHelper(this.root, val);
    }

    private TreeNode insertHelper(TreeNode node, int val) {
        if (node == null) {
            return new TreeNode(val);
        }
        if (val < node.val) {
            node.left = insertHelper(node.left, val);
        } else {
            node.right = insertHelper(node.right, val);
        }
        return node;
    }

    public int delete() {
        if (this.root == null) {
            throw new IllegalStateException("Priority queue is empty");
        }

        int maxVal = findMax(this.root).val;
        this.root = deleteNode(this.root, maxVal);
        return maxVal;
    }

    private TreeNode findMax(TreeNode node) {
        while (node.right != null) {
            node = node.right;
        }
        return node;
    }

    private TreeNode deleteNode(TreeNode node, int val) {
        if (node == null) {
            return null;
        }
        if (val < node.val) {
            node.left = deleteNode(node.left, val);
        } else if (val > node.val) {
            node.right = deleteNode(node.right, val);
        } else {
            if (node.left == null) {
                return node.right;
            }
            if (node.right == null) {
                return node.left;
            }

            TreeNode temp = findMax(node.left);
            node.val = temp.val;
            node.left = deleteNode(node.left, temp.val);
        }
        return node;
    }

    public boolean isEmpty() {
        return this.root == null;
    }

    // Example usage
    public static void main(String[] args) {
        PriorityQueueBST pq = new PriorityQueueBST();
        pq.insert(10);
        pq.insert(20);
        pq.insert(5);
        pq.insert(15);

        while (!pq.isEmpty()) {
            System.out.println(pq.delete());
        }
    }
}
    

class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

class PriorityQueueBST {
    constructor() {
        this.root = null;
    }

    insert(val) {
        const helper = (node, val) => {
            if (!node) {
                return new TreeNode(val);
            }
            if (val < node.val) {
                node.left = helper(node.left, val);
            } else {
                node.right = helper(node.right, val);
            }
            return node;
        };

        this.root = helper(this.root, val);
    }

    delete() {
        const findMax = (node) => {
            while (node.right) {
                node = node.right;
            }
            return node;
        };

        const deleteNode = (node, val) => {
            if (!node) {
                return null;
            }
            if (val < node.val) {
                node.left = deleteNode(node.left, val);
            } else if (val > node.val) {
                node.right = deleteNode(node.right, val);
            } else {
                if (!node.left) {
                    return node.right;
                }
                if (!node.right) {
                    return node.left;
                }
                const temp = findMax(node.left);
                node.val = temp.val;
                node.left = deleteNode(node.left, temp.val);
            }
            return node;
        };

        if (!this.root) {
            return null;
        }
        const maxVal = findMax(this.root).val;
        this.root = deleteNode(this.root, maxVal);
        return maxVal;
    }

    isEmpty() {
        return this.root === null;
    }
}
// Example usage:
const pq = new PriorityQueueBST();
pq.insert(10);
pq.insert(20);
pq.insert(5);
pq.insert(15);

while (!pq.isEmpty()) {
    console.log(pq.delete());
}