heap

Documentation

Overview

Package heap implements a very similar function to the builtin heap(priority queue) package except the elements are not necessarily interface{}, but can be any type.

The trick is using the last element as the in/out place. Push/Pop/Remove are replaced with PushLast/PopToLast/RemoveToLast, respectively. An heap with int value can be easily implemented as follow:

type IntHeap []int
func (h *IntHeap) Pop() int {
    heap.PopToLast(sort.IntSlice(*h))
    res := (*h)[len(*h) - 1]
    *h = (*h)[:len(*h) - 1]

    return res
}

func (h *IntHeap) Push(x int) {
    *h = append(*h, x)
    heap.PushLast(sort.IntSlice(*h))
}

(This package has been moved to github.com/golangplus/container/heap)

Index

• func Init(h sort.Interface)
• func PopToLast(h sort.Interface)
• func PushLast(h sort.Interface)
• func RemoveToLast(h sort.Interface, i int)

Functions

func Init

func Init(h sort.Interface)

A non-empty 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 PopToLast

func PopToLast(h sort.Interface)

Pop removes the minimum element (according to Less) from the heap and place it at the last element of the heap. The complexity is O(log(n)) where n = h.Len().

Same as Remove(h, 0).

NOTE You need to remove the last element after calling to this method.

func PushLast

func PushLast(h sort.Interface)

Push pushes the last element of the heap, which is considered not as the part of the heap, onto the heap. The complexity is

O(log(n)) where n = h.Len().

NOTE You need to append the element to be pushed as the last element before calling to this method.

func RemoveToLast

func RemoveToLast(h sort.Interface, i int)

Remove removes the element at index i from the heap and place it at the last element of the heap.

The complexity is O(log(n)) where n = h.Len().

NOTE You need to remove the last element after calling to this method.