README
¶
heap
A generic binary heap data structure in Go.
It works with any type as long as you provide a comparison function.
The package defines two example functions for building a Max or Min Heap of integers.
Examples
- Heapsort
func main() {
values := []interface{}{40, 30, 50, 100, 15}
// You can specify an initial capacity for the heap,
// len(values) in this case, which helps to avoid reallocations.
// Also, this heap uses the package defined MinInt comparison function,
// that builds a MinHeap of integers
h := heap.New(values, len(values), heap.MinInt)
var sorted []int
for !h.IsEmpty() {
v, err := h.Extract()
if err != nil {
log.Fatal(err)
}
sorted = append(sorted, v.(int))
}
fmt.Println(sorted) // [15 30 40 50 100]
}
Documentation
¶
Overview ¶
Example (HeapSort) ¶
This example shows a use in the Heapsort algorithm
package main
import (
"fmt"
"log"
"github.com/fsmiamoto/heap"
)
func main() {
values := []interface{}{40, 30, 50, 100, 15}
h := heap.New(values, len(values), heap.MinInt)
var sorted []int
for !h.IsEmpty() {
v, err := h.Extract()
if err != nil {
log.Fatal(err)
}
sorted = append(sorted, v.(int))
}
fmt.Println(sorted)
}
Output: [15 30 40 50 100]
Example (Items) ¶
This example shows how to implement your own CompareFunc and the use on a defined type
package main
import (
"fmt"
"log"
"github.com/fsmiamoto/heap"
)
// Item is an example defined type
type Item struct {
key int
}
// MaxItem is an example CompareFunc that builds a MaxHeap using the key property
func MaxItem(node, child interface{}) bool {
return child.(Item).key > node.(Item).key
}
// This example shows how to implement your own CompareFunc and the use on
// a defined type
func main() {
values := []interface{}{
Item{key: 8},
Item{key: 22},
Item{key: 3},
Item{key: 14},
Item{key: 22},
}
h := heap.New(values, len(values), MaxItem)
for !h.IsEmpty() {
i, err := h.Extract()
if err != nil {
log.Fatal(err)
}
fmt.Println(i.(Item).key)
}
}
Output: 22 22 14 8 3
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
Types ¶
type CompareFunc ¶
type CompareFunc func(node, child interface{}) bool
CompareFunc is a function signature used for comparisons between a node and it's children, returning true if the two should be swapped
type Heap ¶
type Heap struct {
// contains filtered or unexported fields
}
Heap is a representation of a binary heap data structure
func New ¶
func New(elements []interface{}, initialCapacity int, cf CompareFunc) *Heap
New creates a heap using the elements of the slice, with the provided capacity, and using the CompareFunc for any comparison between elements Since the heap uses a slice underneath, you can specify a initial capacity for it. The time complexity of building the heap is O(n), n = len(elements)
func (*Heap) Extract ¶
Extract returns the element at the root of the heap The time complexity is O(log(n)), n = # of elements in the heap
Source Files