How do I implement a heap in Go?

A heap is a specialized tree-based data structure that satisfies the heap property. In Go, you can implement a heap using the heap package from the standard library. Below is an example of how to implement a min-heap in Go.

Keywords: Go, Heap, Data Structure, Min-Heap, Go Implementation, Go Programming

Description: This article provides an example of implementing a min-heap in Go using the heap package, showcasing how to manage a collection of elements efficiently.


    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.
	index    int    // The index of the item in the heap.
}

// 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, not lowest, 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]
	pq[i].index = i
	pq[j].index = j
}

// Push adds an item to the queue.
func (pq *PriorityQueue) Push(x interface{}) {
	n := len(*pq)
	item := x.(*Item)
	item.index = n
	*pq = append(*pq, item)
}

// Pop removes the highest priority item from the queue.
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 some items.
	pq := make(PriorityQueue, 0)
	heap.Init(&pq)
	heap.Push(&pq, &Item{
		value:    "task1",
		priority: 3,
	})
	heap.Push(&pq, &Item{
		value:    "task2",
		priority: 1,
	})
	heap.Push(&pq, &Item{
		value:    "task3",
		priority: 2,
	})

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

How do I implement a heap in Go?

Popular Topics

Recent Languages

How do I implement a heap in Go?

Related Questions

Popular Topics

Recent Languages