top

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

Imported by 4 package(s)

  1. github.com/c4e8ece0/gcse/server
  2. github.com/daviddengcn/gcse/server
  3. github.com/mhutter/gcse/pipelines/spider
  4. github.com/mhutter/gcse/server

Test imports 1 package(s)

  1. github.com/golangplus/testing/assert