Priority Queues are abstract data structures where each element has a priority. Elements with higher priority are dequeued before those with lower priority. In this article, we will explore implementing a priority queue in the Go programming language using the standard library's map data structure.
Basic Implementation of Priority Queue in Go
We start by creating a simple priority queue using a map where keys are the priorities and values are slices of values with those priorities.
package main
import (
"fmt"
)
type PriorityQueue map[int][]interface{}
func NewPriorityQueue() PriorityQueue {
return make(PriorityQueue)
}
func (pq PriorityQueue) Enqueue(priority int, value interface{}) {
pq[priority] = append(pq[priority], value)
}
func (pq PriorityQueue) Dequeue() (interface{}, bool) {
for priority := 10; priority >= 0; priority-- { // Assume priorities from 0 to 10
if vals, exists := pq[priority]; exists && len(vals) > 0 {
pq[priority] = vals[1:]
return vals[0], true
}
}
return nil, false
}
func main() {
pq := NewPriorityQueue()
pq.Enqueue(1, "low priority")
pq.Enqueue(5, "medium priority")
pq.Enqueue(10, "high priority")
if value, ok := pq.Dequeue(); ok {
fmt.Println("Dequeued:", value)
}
}Intermediate: Handling Dynamic Priorities
In a more sophisticated implementation, we want to dynamically track and manage priorities without hardcoding them as demonstrated above. This requires maintaining a list of current priorities.
package main
import (
"fmt"
"sort"
)
type PriorityQueue struct {
items map[int][]interface{}
priorities []int
}
func NewPriorityQueue() *PriorityQueue {
return &PriorityQueue{
items: make(map[int][]interface{}),
priorities: []int{},
}
}
func (pq *PriorityQueue) Enqueue(priority int, value interface{}) {
pq.items[priority] = append(pq.items[priority], value)
if !pq.contains(pq.priorities, priority) {
pq.priorities = append(pq.priorities, priority)
sort.Sort(sort.Reverse(sort.IntSlice(pq.priorities)))
}
}
func (pq *PriorityQueue) Dequeue() (interface{}, bool) {
for _, priority := range pq.priorities {
if vals := pq.items[priority]; len(vals) > 0 {
pq.items[priority] = vals[1:]
return vals[0], true
}
}
return nil, false
}
func (pq *PriorityQueue) contains(slice []int, item int) bool {
for _, v := range slice {
if v == item {
return true
}
}
return false
}
func main() {
pq := NewPriorityQueue()
pq.Enqueue(2, "Item A")
pq.Enqueue(3, "Item B")
pq.Enqueue(1, "Item C")
fmt.Println("Dequeue result:")
for v, ok := pq.Dequeue(); ok; v, ok = pq.Dequeue() {
fmt.Println(v)
}
}Advanced: Thread-Safe Implementation
In a concurrent environment, Go's channels or mutex can be utilized to make the priority queue thread-safe. The code below demonstrates this using a mutex.
package main
import (
"fmt"
"sync"
)
type PriorityQueue struct {
items map[int][]interface{}
priorities []int
lock sync.Mutex
}
func NewPriorityQueue() *PriorityQueue {
return &PriorityQueue{
items: make(map[int][]interface{}),
priorities: []int{},
lock: sync.Mutex{},
}
}
func (pq *PriorityQueue) Enqueue(priority int, value interface{}) {
pq.lock.Lock()
defer pq.lock.Unlock()
pq.items[priority] = append(pq.items[priority], value)
if !contains(pq.priorities, priority) {
pq.priorities = append(pq.priorities, priority)
sort.Sort(sort.Reverse(sort.IntSlice(pq.priorities)))
}
}
func (pq *PriorityQueue) Dequeue() (interface{}, bool) {
pq.lock.Lock()
defer pq.lock.Unlock()
for _, priority := range pq.priorities {
if vals := pq.items[priority]; len(vals) > 0 {
pq.items[priority] = vals[1:]
return vals[0], true
}
}
return nil, false
}
func contains(slice []int, item int) bool {
for _, v := range slice {
if v == item {
return true
}
}
return false
}
func main() {
pq := NewPriorityQueue()
pq.Enqueue(3, "low priority")
pq.Enqueue(2, "medium priority")
pq.Enqueue(1, "high priority")
fmt.Println("Dequeue time:")
for v, ok := pq.Dequeue(); ok; v, ok = pq.Dequeue() {
fmt.Println(v)
}
}This version of the priority queue introduces locking to ensure that concurrent access to the queue doesn't cause inconsistent or corrupted data states. This is essential for any multi-threaded application in Go.
