How do I implement a priority queue in Go?

A priority queue is an abstract data type where each element has a priority associated with it. Elements with higher priority are served before elements with lower priority. In Go, you can implement a priority queue using a min-heap or max-heap. Below is an example of how to implement a priority queue using Go's heap package.


package main

import (
    "container/heap"
    "fmt"
)

// An Item is something we manage in a priority queue.
type Item struct {
    value    string // The value of the item; arbitrary.
    priority int    // The priority of the item in the queue.
}

// A PriorityQueue implements heap.Interface and holds Items.
type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
    // We want Pop to give us the highest priority, so we use greater than here.
    return pq[i].priority > pq[j].priority
}

func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(x interface{}) {
    item := x.(*Item)
    *pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    *pq = old[0 : n-1]
    return item
}

func main() {
    // Create a priority queue and add items
    pq := make(PriorityQueue, 0)
    heap.Init(&pq)
    
    heap.Push(&pq, &Item{value: "low priority", priority: 1})
    heap.Push(&pq, &Item{value: "medium priority", priority: 5})
    heap.Push(&pq, &Item{value: "high priority", priority: 10})

    // Take items from the priority queue
    for pq.Len() > 0 {
        item := heap.Pop(&pq).(*Item)
        fmt.Printf("%s with priority %d\n", item.value, item.priority)
    }
}

How do I implement a priority queue in Go?

Popular Topics

Recent Languages

How do I implement a priority queue in Go?

Related Questions

Popular Topics

Recent Languages