container: github.com/golangplus/container/heap Index | Files

package heap

import "github.com/golangplus/container/heap"

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

The trick is to use the last element as the in/out place. Push/Pop/Remove are replaced with PushLast/PopToLast/RemoveToLast, respectively.

A 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))
}

Use of the IntHeap:

hp := IntHeap{3, 1, 5}
heap.Init(sort.Interface(h))
hp.Push(4)
...
value := hp.Pop()

PushLastF/PopToLastF/RemoveToLastF takes funcs other than sort.Interface as the argument. E.g., a heap with type T value can be implemented as follow:

type THeap []T
func (h *THeap) Pop() T {
  heap.PopToLastF(len(*h), func(i, j int) bool {
    ti, tj := (*h)[i], (*h)h[j]
    // return whether ti < tj
  }, func(i, j int) {
    (*h)[i], (*h)[j] = (*h)[j], (*h)[i]
  })

  res := (*h)[len(*h) - 1]
  *h = (*h)[:len(*h) - 1]

  return res
}

func (h *THeap) Push(x T) {
  *h = append(*h, x)
  heap.PushLastF(len(*h), func(i, j int) bool {
    ti, tj := (*h)[i], (*h)h[j]
    // return whether ti < tj
  }, func(i, j int) {
    (*h)[i], (*h)[j] = (*h)[j], (*h)[i]
  })
}

Index

Package Files

float64s.go heap.go interfaces.go ints.go strings.go

func Fix Uses

func Fix(h sort.Interface, index int)

Fix re-establishes the heap ordering after the value of the element at the index has changed. Changing the value of the element at the index and then calling Fix is equivalent to, but less expensive than, calling RemoveToLast(h, index) followed by a PushLast. The complexity is O(log(N)), where N = h.Len().

func FixF Uses

func FixF(Len int, Less func(i, j int) bool, Swap func(i, j int), index int)

Similar to Fix but with interface provided by funcs.

func Init Uses

func Init(h sort.Interface)

Init heapifies a non-empty array defined by the sort.Interface. The complexity is O(N), where N = h.Len().

func InitF Uses

func InitF(Len int, Less func(i, j int) bool, Swap func(i, j int))

Similar to Init but with interface provided by funcs.

func PopToLast Uses

func PopToLast(h sort.Interface)

Pop removes the minimum element (according to Less) from the heap and place it as 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 PopToLastF Uses

func PopToLastF(Len int, Less func(i, j int) bool, Swap func(i, j int))

Similar to PopToLast but with interface provided by funcs.

func PushLast Uses

func PushLast(h sort.Interface)

Push pushes the last element of the heap, which was not considered as 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 PushLastF Uses

func PushLastF(Len int, Less func(i, j int) bool, Swap func(i, j int))

Similar to PushLast but with interface provided by funcs.

func RemoveToLast Uses

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.

func RemoveToLastF Uses

func RemoveToLastF(Len int, Less func(i, j int) bool, Swap func(i, j int), i int)

Similar to RemoveToLast but with interface provided by funcs.

type Float64s Uses

type Float64s struct {
    // contains filtered or unexported fields
}

A heap for strings. The pointer to the zero value of Float64s is a heap with default less func which compares string values on the natual order. Use NewFloat64s to customize less func and initial capacity.

func NewFloat64s Uses

func NewFloat64s(less func(x, y float64) bool, cap int) *Float64s

NewFloat64s returns a *Float64s with customized less func and initial capacity.

func (*Float64s) Len Uses

func (h *Float64s) Len() int

Len returns the number of elements in the current heap.

func (*Float64s) Peek Uses

func (h *Float64s) Peek() float64

Peek returns the top most element. It panics if the heap is empty.

func (*Float64s) Pop Uses

func (h *Float64s) Pop() float64

Pop removes the top element from the heap and returns it.

func (*Float64s) PopAll Uses

func (h *Float64s) PopAll() []float64

PopAll pops and returns all elements of the heap in reverse order.

func (*Float64s) Push Uses

func (h *Float64s) Push(x float64)

Push inserts an element to the heap.

type Interfaces Uses

type Interfaces interface {
    // Len returns the number of elements in the current heap.
    Len() int
    // Push inserts an element to the heap.
    Push(x interface{})
    // Pop removes the top element from the heap and returns it.
    Pop() interface{}
    // PopAll pops and returns all elements of the heap in reverse order.
    PopAll() []interface{}
    // Peek returns the top most element. It panics if the heap is empty.
    Peek() interface{}
    // TopNPush inserts an element to the heap if the heap does not reach its
    // capacity. Otherwise, if the top element is less then the new element
    // the top element is removed and the new one is inserted.
    // This method is used to generate a top N largest elements where N is
    // the capacity of the heap.
    TopNPush(x interface{})
    // TopNPopAll is similar to PopAll but keep the capacity of the heap
    // unchanged.
    TopNPopAll() []interface{}
}

A heap for interface{}. Use NewInterfaces to create an instance.

func NewInterfaces Uses

func NewInterfaces(less func(x, y interface{}) bool, cap int) Interfaces

NewInterfaces returns an instance of Interfaces with a customized less func and the initial capacity.

type Ints Uses

type Ints struct {
    // contains filtered or unexported fields
}

A heap for ints. The pointer to the zero value of Ints is a heap with default less func which compares int values on the natual order. Use NewInts to customize less func and initial capacity.

func NewInts Uses

func NewInts(less func(x, y int) bool, cap int) *Ints

NewInts returns a *Ints with customized less func and initial capacity.

func (*Ints) Len Uses

func (h *Ints) Len() int

Len returns the number of elements in the current heap.

func (*Ints) Peek Uses

func (h *Ints) Peek() int

Peek returns the top most element. It panics if the heap is empty.

func (*Ints) Pop Uses

func (h *Ints) Pop() int

Pop removes the top element from the heap and returns it.

func (*Ints) PopAll Uses

func (h *Ints) PopAll() []int

PopAll pops and returns all elements of the heap in reverse order.

func (*Ints) Push Uses

func (h *Ints) Push(x int)

Push inserts an element to the heap.

type Strings Uses

type Strings struct {
    // contains filtered or unexported fields
}

A heap for strings. The pointer to the zero value of Strings is a heap with default less func which compares string values on the natual order. Use NewStrings to customize less func and initial capacity.

func NewStrings Uses

func NewStrings(less func(x, y string) bool, cap int) *Strings

NewStrings returns a *Strings with a customized less func and the initial capacity.

func (*Strings) Len Uses

func (h *Strings) Len() int

Len returns the number of elements in the current heap.

func (*Strings) Peek Uses

func (h *Strings) Peek() string

Peek returns the top most element. It panics if the heap is empty.

func (*Strings) Pop Uses

func (h *Strings) Pop() string

Pop removes the top element from the heap and returns it.

func (*Strings) PopAll Uses

func (h *Strings) PopAll() []string

PopAll pops and returns all elements of the heap in reverse order.

func (*Strings) Push Uses

func (h *Strings) Push(x string)

Push inserts an element to the heap.

Package heap imports 1 packages (graph) and is imported by 3 packages. Updated 2016-07-19. Refresh now. Tools for package owners.