Priority Queue Implementation in Ruby

1. Introduction

A Priority Queue is an advanced form of a queue where each element is associated with a priority. Elements are dequeued based on their priority rather than their position in the queue. The element with the highest priority is dequeued before elements of lower priority. In cases where two elements have the same priority, they are dequeued based on their order in the queue.

2. Implementation Steps

1. Define the PriorityQueue class and initialize an empty list to store elements and their priorities.

2. Implement the enqueue method to add an element with its priority to the queue.

3. Implement the dequeue method to remove and return the element with the highest priority.

4. Implement the peek method to view the highest-priority element without removing it.

5. Implement a method to check if the priority queue is empty.

3. Implementation in Ruby Programming

class PriorityQueue
    def initialize
        @items = [] # Initializing an empty array to store the queue elements and their priorities
    end
    # A helper method to sort the queue based on priorities
    def sort_by_priority
        @items.sort! { |a, b| b[1] <=> a[1] }
    end
    # Adding an item and its priority to the queue
    def enqueue(item, priority)
        @items.push([item, priority])
        sort_by_priority
    end
    # Removing the highest priority item from the queue
    def dequeue
        @items.shift[0]
    end
    # Viewing the highest priority item without removing it
    def peek
        @items.first[0]
    end
    # Checking if the queue is empty
    def is_empty?
        @items.empty?
    end
end
# Client code
pq = PriorityQueue.new
pq.enqueue("Task A", 2)
pq.enqueue("Task B", 1)
pq.enqueue("Task C", 3)
puts "Highest priority task: #{pq.peek}"  # Output: Task C
puts "Removing highest priority task: #{pq.dequeue}"  # Output: Task C
puts "Now, highest priority task: #{pq.peek}"  # Output: Task A

Output:

Highest priority task: Task C
Removing highest priority task: Task C
Now, highest priority task: Task A

Explanation:

1. The PriorityQueue class is initialized with an empty array @items to store the queue's elements and their priorities.

2. The sort_by_priority method sorts the @items array based on the priority. The highest priority item is placed at the front.

3. The enqueue method adds an element and its priority to the @items array and then sorts it based on priority.

4. The dequeue method removes and returns the first element (highest priority) from the @items array.

5. The peek method returns the first element (highest priority) from the @items array without removing it.

6. The is_empty? method checks if the @items array is empty, indicating that the priority queue is empty.