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

Key Takeaways

1. Go does not have a built-in priority queue, but you can implement one using the container/heap package.
2. Priority is controlled by customizing the Less() method to define heap order (min-heap or max-heap).
3. The heap interface requires implementing sorting and queue mutation methods (Push, Pop, etc.).

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.

FAQs

Can Go’s heap.Interface be used for both min-heap and max-heap?

Yes, by customizing the Less() function. For a max-heap, return i > j; for a min-heap, return i < j.

Why is an index field needed in the Item struct?

The index helps heap.Fix efficiently update the position of an element when its priority changes.

Is heap.Pop() guaranteed to return the highest-priority item?

Yes, if Less() is defined appropriately for a max-heap.

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