Implementing a Priority Queue in Go Using `container/heap`

A priority queue is an abstract data structure where each element has an associated priority. Elements are served based on their priority, with higher-priority elements dequeued before lower-priority ones. In Go, the container/heap package provides a way to implement a priority queue by using a heap interface.

Understanding the Heap Interface

The container/heap package operates on types that implement the heap.Interface. This interface requires the following methods:

type Interface interface {
    sort.Interface
    Push(x any) // add x as element Len()
    Pop() any   // remove and return element Len() - 1.
}

By implementing this interface, you can define custom behavior for your priority queue.

Implementing a Priority Queue

To create a priority queue, define a struct for the items you want to store, including a priority field. Then, implement the heap.Interface on a slice of pointers to these items.

package main

import (
    "container/heap"
    "fmt"
)

// Item represents an element in the priority queue.
type Item struct {
    value    string // The value of the item.
    priority int    // The priority of the item.
    index    int    // The index of the item in the heap.
}

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

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

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

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

func (pq *PriorityQueue) Push(x any) {
    n := len(*pq)
    item := x.(*Item)
    item.index = n
    *pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() any {
    old := *pq
    n := len(old)
    item := old[n-1]
    item.index = -1 // for safety
    *pq = old[0 : n-1]
    return item
}

// update modifies the priority and value of an Item in the queue.
func (pq *PriorityQueue) update(item *Item, value string, priority int) {
    item.value = value
    item.priority = priority
    heap.Fix(pq, item.index)
}

func main() {
    // Create a priority queue and add some items.
    pq := make(PriorityQueue, 0)
    heap.Init(&pq)

    items := map[string]int{
        "banana": 3,
        "apple":  2,
        "pear":   4,
    }

    for value, priority := range items {
        heap.Push(&pq, &Item{
            value:    value,
            priority: priority,
        })
    }

    // Update the priority of an item.
    item := &Item{
        value:    "orange",
        priority: 1,
    }
    heap.Push(&pq, item)
    pq.update(item, item.value, 5)

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

This example demonstrates how to implement a priority queue in Go using the container/heap package. By customizing the Less method, you can define whether your priority queue behaves as a min-heap or max-heap. In this case, we used a max-heap to ensure that higher-priority items are dequeued first.

We are Leapcell, your top choice for hosting Go projects.

Leapcell is the Next-Gen Serverless Platform for Web Hosting, Async Tasks, and Redis:

Multi-Language Support

• Develop with Node.js, Python, Go, or Rust.

Deploy unlimited projects for free

• pay only for usage — no requests, no charges.

Unbeatable Cost Efficiency

• Pay-as-you-go with no idle charges.
• Example: $25 supports 6.94M requests at a 60ms average response time.

Streamlined Developer Experience

• Intuitive UI for effortless setup.
• Fully automated CI/CD pipelines and GitOps integration.
• Real-time metrics and logging for actionable insights.

Effortless Scalability and High Performance

• Auto-scaling to handle high concurrency with ease.
• Zero operational overhead — just focus on building.

Explore more in the Documentation!

Follow us on X: @LeapcellHQ