go-villa: github.com/daviddengcn/go-villa/heap Index | Files

package heap

import "github.com/daviddengcn/go-villa/heap"

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

Package Files

heap.go

func Init Uses

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 Uses

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 Uses

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 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.

Package heap imports 1 packages (graph). Updated 2016-07-28. Refresh now. Tools for package owners. This is an inactive package (no imports and no commits in at least two years).