Published on

# Implementing a Priority Queue Using Heap in Go

Authors

## Introduction

In computer science, a priority queue is an abstract data type that stores elements with priorities. It allows elements with higher priorities to be dequeued first. Priority queues are widely used in many algorithms such as Dijkstra's shortest path algorithm, Prim's minimum spanning tree algorithm, Huffman coding, and many more. In this blog post, we will explore how to implement a priority queue using a heap in the Go programming language.

## Heap Data Structure

A heap is a tree-based data structure that satisfies the heap property. In a heap, every parent node has a priority greater than or equal to its children. There are two types of heaps: max heaps and min heaps. In a max heap, the root node has the highest priority, and in a min heap, the root node has the lowest priority.

A heap can be represented using an array. The root node is stored in the first index of the array, and its left and right children are stored in the second and third indices, respectively. The left child of a node at index `i` is located at index `2i`, and the right child is located at index `2i+1`. The parent of a node at index `i` is located at index `i/2`.

## Priority Queue Implementation Using Heap in Go

In Go, we can implement a priority queue using the `container/heap` package. The package provides an interface for heap operations such as pushing, popping, and updating elements. To use the container/heap package, we need to implement the heap.Interface interface.

The `heap.Interface` interface requires three methods to be implemented: `Len()`, `Less()`, and `Swap()`. `Len()` returns the length of the heap, `Less()` returns `true` if the element at index `i` has a higher priority than the element at index `j`, and Swap() swaps the elements at indices `i` and `j`.

Here is an implementation of a priority queue using a max heap in Go:

`_101package main_101_101import (_101 "container/heap"_101 "fmt"_101)_101_101// An Item is something we manage in a priority queue._101type Item struct {_101 value string // The value of the item; arbitrary._101 priority int // The priority of the item in the queue._101 // The index is needed by update and is maintained by the heap.Interface methods._101 index int // The index of the item in the heap._101}_101_101// A PriorityQueue implements heap.Interface and holds Items._101type PriorityQueue []*Item_101_101func (pq PriorityQueue) Len() int { return len(pq) }_101_101func (pq PriorityQueue) Less(i, j int) bool {_101 // We want Pop to give us the highest, not lowest, priority so we use greater than here._101 return pq[i].priority > pq[j].priority_101}_101_101func (pq PriorityQueue) Swap(i, j int) {_101 pq[i], pq[j] = pq[j], pq[i]_101 pq[i].index = i_101 pq[j].index = j_101}_101_101func (pq *PriorityQueue) Push(x any) {_101 n := len(*pq)_101 item := x.(*Item)_101 item.index = n_101 *pq = append(*pq, item)_101}_101_101func (pq *PriorityQueue) Pop() any {_101 old := *pq_101 n := len(old)_101 item := old[n-1]_101 old[n-1] = nil // avoid memory leak_101 item.index = -1 // for safety_101 *pq = old[0 : n-1]_101 return item_101}_101_101// update modifies the priority and value of an Item in the queue._101func (pq *PriorityQueue) update(item *Item, value string, priority int) {_101 item.value = value_101 item.priority = priority_101 heap.Fix(pq, item.index)_101}_101_101// This example creates a PriorityQueue with some items, adds and manipulates an item,_101// and then removes the items in priority order._101func main() {_101 // Some items and their priorities._101 items := map[string]int{_101 "banana": 3, "apple": 2, "pear": 4,_101 }_101_101 // Create a priority queue, put the items in it, and_101 // establish the priority queue (heap) invariants._101 pq := make(PriorityQueue, len(items))_101 i := 0_101 for value, priority := range items {_101 pq[i] = &Item{_101 value: value,_101 priority: priority,_101 index: i,_101 }_101 i++_101 }_101 heap.Init(&pq)_101_101 // Insert a new item and then modify its priority._101 item := &Item{_101 value: "orange",_101 priority: 1,_101 }_101 heap.Push(&pq, item)_101 pq.update(item, item.value, 5)_101_101 // Take the items out; they arrive in decreasing priority order._101 for pq.Len() > 0 {_101 item := heap.Pop(&pq).(*Item)_101 fmt.Printf("%.2d:%s \n", item.priority, item.value)_101 }_101}_101_101/*_101Output:_101_10105:orange _10104:pear _10103:banana _10102:apple_101_101*/`

## Conclusion

Implementing a priority queue using a heap in Go is straightforward using the `container/heap` package. Priority queues are useful in many algorithms, and understanding how to implement them using a heap can improve the efficiency of your programs. With the example above, you should now have a good understanding of how to use a priority queue in your Go programs.