package heap

Import Path
	container/heap (on go.dev)

Dependency Relation
	imports one package, and imported by 2 packages


Involved Source Files

	
		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
		minimum-valued node in its subtree.
		
		The minimum element in the tree is the root, at index 0.
		
		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_pq_test.go has the complete source.


Code Examples

	
		// This example demonstrates an integer heap built using the heap interface.
		package main
		
		import (
			"container/heap"
			"fmt"
		)
		
		// An IntHeap is a min-heap of ints.
		type IntHeap []int
		
		func (h IntHeap) Len() int           { return len(h) }
		func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
		func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
		
		func (h *IntHeap) Push(x any) {
			// Push and Pop use pointer receivers because they modify the slice's length,
			// not just its contents.
			*h = append(*h, x.(int))
		}
		
		func (h *IntHeap) Pop() any {
			old := *h
			n := len(old)
			x := old[n-1]
			*h = old[0 : n-1]
			return x
		}
		
		// This example inserts several ints into an IntHeap, checks the minimum,
		// and removes them in order of priority.
		func main() {
			h := &IntHeap{2, 1, 5}
			heap.Init(h)
			heap.Push(h, 3)
			fmt.Printf("minimum: %d\n", (*h)[0])
			for h.Len() > 0 {
				fmt.Printf("%d ", heap.Pop(h))
			}
		}

	
		// 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 update 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 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]
			old[n-1] = nil  // don't stop the GC from reclaiming the item eventually
			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)
		}
		
		// This example creates a PriorityQueue with some items, adds and manipulates an item,
		// and then removes the items in priority order.
		func main() {
			// Some items and their priorities.
			items := map[string]int{
				"banana": 3, "apple": 2, "pear": 4,
			}
		
			// Create a priority queue, put the items in it, and
			// establish the priority queue (heap) invariants.
			pq := make(PriorityQueue, len(items))
			i := 0
			for value, priority := range items {
				pq[i] = &Item{
					value:    value,
					priority: priority,
					index:    i,
				}
				i++
			}
			heap.Init(&pq)
		
			// Insert a new item and then modify its priority.
			item := &Item{
				value:    "orange",
				priority: 1,
			}
			heap.Push(&pq, item)
			pq.update(item, item.value, 5)
		
			// Take the items out; they arrive in decreasing priority order.
			for pq.Len() > 0 {
				item := heap.Pop(&pq).(*Item)
				fmt.Printf("%.2d:%s ", item.priority, item.value)
			}
		}




Package-Level Type Names (only one)


	/* sort by:  |  */
	
		The Interface type describes the requirements
		for a type using the routines in this package.
		Any type that implements it 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 2*i+1 <= j <= 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].

		
			
				Len is the number of elements in the collection.

			
				Less reports whether the element with index i
				must sort before the element with index j.
				
				If both Less(i, j) and Less(j, i) are false,
				then the elements at index i and j are considered equal.
				Sort may place equal elements in any order in the final result,
				while Stable preserves the original input order of equal elements.
				
				Less must describe a transitive ordering:
				 - if both Less(i, j) and Less(j, k) are true, then Less(i, k) must be true as well.
				 - if both Less(i, j) and Less(j, k) are false, then Less(i, k) must be false as well.
				
				Note that floating-point comparison (the < operator on float32 or float64 values)
				is not a transitive ordering when not-a-number (NaN) values are involved.
				See Float64Slice.Less for a correct implementation for floating-point values.

			
				// remove and return element Len() - 1.

			
				// add x as element Len()

			
				Swap swaps the elements with indexes i and j.

		
			 Interface : sort.Interface
		
			func Fix(h Interface, i int)
			func Init(h Interface)
			func Pop(h Interface) any
			func Push(h Interface, x any)
			func Remove(h Interface, i int) any




Package-Level Functions (total 5)


	
		Fix re-establishes the heap ordering after the element at index i has changed its value.
		Changing the value of the element at index i and then calling Fix is equivalent to,
		but less expensive than, calling [Remove](h, i) followed by a Push of the new value.
		The complexity is O(log n) where n = h.Len().


	
		Init establishes the heap invariants required by the other routines in this package.
		Init is idempotent with respect to the heap invariants
		and may be called whenever the heap invariants may have been invalidated.
		The complexity is O(n) where n = h.Len().


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


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


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