Version: v0.0.0-...-be291eb Latest Latest

This package is not in the latest version of its module.

Go to latest
Published: May 4, 2022 License: MIT Imports: 0 Imported by: 0



Package heap provides heap operations for a type A and a comparison function Less. 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.

This provides a min-heap with the following invariants (established after Init has been called or if the data is empty or sorted):

!Less(h[j], h[i]) for 0 <= i < len(h) and j = 2*i+1 or 2*i+2 and j < len(h)

A heap is a common way to implement a priority queue. To build a priority queue, use 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.

Example (IntHeap)

This example inserts several ints into an IntHeap, checks the minimum, and removes them in order of priority.

package main

import (


func main() {
	h := &heap.Heap{2, 1, 5}
	fmt.Printf("minimum: %d\n", (*h)[0])
	for len(*h) > 0 {
		fmt.Printf("%d ", h.Pop())

minimum: 1
1 2 3 5




This section is empty.


This section is empty.


func Less

func Less(a A, b A) bool

Less is a function to compare two As


type A

type A int

An A is the element in the slice []A we are keeping as a heap

template type Heap(A, Less)

type Heap

type Heap []A

Heap stored in an slice

func (*Heap) Fix

func (h *Heap) Fix(i int)

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 h.Remove(i) followed by a Push of the new value. The complexity is O(log(n)) where n = len(h).

func (*Heap) Init

func (h *Heap) Init()

Init is compulsory 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 = len(h).

func (*Heap) Pop

func (h *Heap) Pop() A

Pop removes the minimum element (according to Less) from the heap and returns it. The complexity is O(log(n)) where n = len(h). It is equivalent to h.Remove(0).

func (*Heap) Push

func (h *Heap) Push(x A)

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

func (*Heap) Remove

func (h *Heap) Remove(i int) A

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

Source Files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL