heap

Documentation

Overview

Package heap provides heap operations for any type that implements heap.Interface. A heap is a tree with the property that each node is the highest-valued node in its subtree.

A heap is a common way to implement a priority queue. To build a priority queue, implement the Heap interface with the (negative) priority as the ordering for the Less method, so Push adds items while Pop removes the highest-priority item from the queue. The Examples include such an implementation; the file example_test.go has the complete source.

Example

This example pushes 10 items into a PriorityQueue and takes them out in order of priority.

// This example demonstrates a priority queue built using the heap interface.
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.
	// The index is needed by changePriority and is maintained by the heap.Interface methods.
	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
}

func (pq *PriorityQueue) Push(x interface{}) {
	// Push and Pop use pointer receivers because they modify the slice's length,
	// not just its contents.
	n := len(*pq)
	item := x.(*Item)
	item.index = n
	*pq = append(*pq, item)
}

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

// update is not used by the example but shows how to take the top item from
// the queue, update its priority and value, and put it back.
func (pq *PriorityQueue) update(value string, priority int) {
	item := heap.Pop(pq).(*Item)
	item.value = value
	item.priority = priority
	heap.Push(pq, item)
}

// changePriority is not used by the example but shows how to change the
// priority of an arbitrary item.
func (pq *PriorityQueue) changePriority(item *Item, priority int) {
	heap.Remove(pq, item.index)
	item.priority = priority
	heap.Push(pq, item)
}

// This example pushes 10 items into a PriorityQueue and takes them out in
// order of priority.
func main() {
	const nItem = 10
	// Random priorities for the items (a permutation of 0..9, times 11)).
	priorities := [nItem]int{
		77, 22, 44, 55, 11, 88, 33, 99, 00, 66,
	}
	values := [nItem]string{
		"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine",
	}
	// Create a priority queue and put some items in it.
	pq := make(PriorityQueue, 0, nItem)
	for i := 0; i < cap(pq); i++ {
		item := &Item{
			value:    values[i],
			priority: priorities[i],
		}
		heap.Push(&pq, item)
	}
	// Take the items out; should arrive in decreasing priority order.
	// For example, the highest priority (99) is the seventh item, so output starts with 99:"seven".
	for i := 0; i < nItem; i++ {
		item := heap.Pop(&pq).(*Item)
		fmt.Printf("%.2d:%s ", item.priority, item.value)
	}
}

Output:

99:seven 88:five 77:zero 66:nine 55:three 44:two 33:six 22:one 11:four 00:eight

Index

• func Init(h Interface)
• func Pop(h Interface) interface{}
• func Push(h Interface, x interface{})
• func Remove(h Interface, i int) interface{}
• type Interface

Examples

• Package

Functions

func Init

func Init(h Interface)

A heap must be initialized before any of the heap operations can be used. Init is idempotent with respect to the heap invariants and may be called whenever the heap invariants may have been invalidated. Its complexity is O(n) where n = h.Len().

func Pop

func Pop(h Interface) interface{}

Pop removes the minimum element (according to Less) from the heap and returns it. The complexity is O(log(n)) where n = h.Len(). Same as Remove(h, 0).

func Push

func Push(h Interface, x interface{})

Push pushes the element x onto the heap. The complexity is O(log(n)) where n = h.Len().

func Remove

func Remove(h Interface, i int) interface{}

Remove removes the element at index i from the heap. The complexity is O(log(n)) where n = h.Len().

Types

type Interface

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

Any type that implements heap.Interface may be used as a min-heap with the following invariants (established after Init has been called or if the data is empty or sorted):

!h.Less(j, i) for 0 <= i < h.Len() and j = 2*i+1 or 2*i+2 and j < h.Len()

Note that Push and Pop in this interface are for package heap's implementation to call. To add and remove things from the heap, use heap.Push and heap.Pop.