Priority Queue Implementation in Golang

1. Introduction

A Priority Queue is an advanced version of a regular queue. Instead of following a strict FIFO (First In First Out) order, elements in a Priority Queue are assigned a priority. Elements with higher priority are dequeued before elements with lower priority. In the event of a tie in priority, they are dequeued in the order they were added.

2. Implementation Steps

1. Define a Item type with two fields: value and priority.

2. Define a PriorityQueue type as a slice of Item.

3. Implement an Enqueue method to add an item based on its priority.

4. Implement a Dequeue method to remove and return the highest-priority item. Handle queue underflow.

5. Optionally, add a method to peek at the highest-priority item without dequeuing it.

3. Implementation in Golang

package main
import (
	"errors"
	"fmt"
	"sort"
)
type Item struct {
	value    string
	priority int
}
type PriorityQueue []*Item
func (pq *PriorityQueue) Enqueue(value string, priority int) {
	item := &Item{
		value:    value,
		priority: priority,
	}
	*pq = append(*pq, item)
	sort.SliceStable(*pq, func(i, j int) bool {
		return (*pq)[i].priority > (*pq)[j].priority
	})
}
func (pq *PriorityQueue) Dequeue() (string, error) {
	if len(*pq) == 0 {
		return "", errors.New("PriorityQueue is empty")
	}
	item := (*pq)[0]
	*pq = (*pq)[1:]
	return item.value, nil
}
func (pq *PriorityQueue) Peek() (string, error) {
	if len(*pq) == 0 {
		return "", errors.New("PriorityQueue is empty")
	}
	item := (*pq)[0]
	return item.value, nil
}
func main() {
	var pq PriorityQueue
	pq.Enqueue("Task 1", 2)
	pq.Enqueue("Task 2", 1)
	pq.Enqueue("Task 3", 3)
	fmt.Println("Peek at top priority item:", pq.Peek())
	deq, _ := pq.Dequeue()
	fmt.Println("Dequeued:", deq)
}

Output:

Peek at top priority item: Task 3
Dequeued: Task 3

Explanation:

1. The Item type is defined to represent an entry in the priority queue. It has two fields: value (a string) and priority (an integer).

2. The PriorityQueue type is a slice of pointers to Item structures.

3. The Enqueue method adds an item to the PriorityQueue and then sorts the entire slice based on priorities. This way, the highest priority item is always at the start of the slice.

4. The Dequeue method checks if the queue is empty. If not, it retrieves the first item (highest priority) and shrinks the slice by one.

5. The Peek method allows users to view the top-priority item without removing it.

6. In the main function, items are added to the queue with different priorities, and then the top-priority item is peeked at and dequeued to showcase the functionality.

The presented PriorityQueue implementation in Golang offers a simple way to utilize priorities in task scheduling and similar applications.