Skip to content

Instantly share code, notes, and snippets.

@avinoamr avinoamr/minheap.go
Last active May 19, 2016

Embed
What would you like to do?
Binary MinHeap exercise implementation in go using a slice to store the tree.
/**
* Binary Heap exercise implementation in go using a slice to store the tree.
*
* A heap is a balanced binary tree, with the invariant that each node is
* smaller then all of its children, thus making the root node the minimal
* value in the tree (MinHeap; in MaxHeap, it's exact reversed). Heaps are
* useful for sorting and priority queues.
* See: https://en.wikipedia.org/wiki/Binary_heap
*
* In order to remove overhead, the heap is represented as an array with the
* root at index 0, and its children are in indices 1 and 2. Formally, the
* children of the node at index N are found at indices (2N + 1) and (2N + 2).
* Inversely, the parent of node at index N is found at N-1/2
*
*/
package main
import "fmt"
/**
* Comparer is an interface for comparable items which is used to keep the heap
* type in-dependent. It's Compare() function result is per qsort()
* convention, ie: <0, 0, >0 according as a<b, a=b, a>b.
*/
type Comparer interface {
Compare(Comparer) int
}
// Heap is just a slice of items that can be compared to one another
// the heap type is internal and shouldn't be used directly - use MinHeap
// or MaxHeap instead. Lower-cased because it's private.
type heap []Comparer
/**
* Push an item to the heap, with the provided direction int.
*
* This implementation supports both MinHeap (smallest at the root) and
* MaxHeap (biggest at the root) by using the inverse int to flip the results
* of the individual comparisons. therefore, inverse should be either 1 or -1.
* The concrete MinHeap and MaxHeap choose the inverse. An alternative approach
* is to reserve the first index in our slice to the inverse value, thus
* supporting both Min and Max heaps within the same interface, with a direction
* setter: h.SetMaxHeap() and h.SetMinHeap()
*
* We must use some pointer trickery here because append() might grow the
* underlying slice and produce a new slice. We want these commands to be
* mutable on the heap, so we must point the original heap to the new slice
* when that happens. An alternative approach might be to use similar semantics
* to append() by returning the new heap: h = h.Push(...). That's risky though
* because, unlike the compiler, we can't guarantee that the returned heap is
* picked up by the caller
*/
func (hptr *heap) Push(i Comparer, inverse int) {
h := *hptr
// we must first append the new value as the last leaf in order to
// ensure we're in bounds. Breaks the invariant.
h = append(h, i)
// sift up the tree from the newly inserted node until we find a location
// for it that will satisfy the invariant that the new item is greater than
// its parent
idx := len(h) - 1
for idx > 0 {
parentIdx := idx / 2
if h[idx].Compare(h[parentIdx]) * inverse > 0 {
break
}
// swap & continue
h[idx], h[parentIdx] = h[parentIdx], h[idx]
idx = parentIdx
}
*hptr = h
}
/**
* Inversely, Pop removes the top item from the heap and returns it, after
* re-organizing the structure such that the new top is now the smaller (or
* biggest) item. Similar to heap.Push(), we accept the inverse to flip the
* individual comparisons.
*
* See note about the pointers in Push(). An alternative approach might be to
* return the pop'ed value and the new heap: value, h := h.Pop()
*/
func (hptr *heap) Pop(inverse int) Comparer {
h := *hptr
n := len(h)
// empty heap
if n == 0 {
return nil
}
// pop the root, at index 0 which will create a "hole" to be filled
idx := 0
root := h[idx] // pop'd value
// replace the pop'ed root with the last item, which will break the
// invariant, and sift down the tree until we find a new location for it
// that will satisfy the invariant re-inserted item is greater than its
// parent
v := h[n-1] // the last leaf needs to be re-inserted
for {
childIdx := idx * 2 + 1
if childIdx >= n {
break; // no children, we're done here.
}
// if we have more than 1 child, compare them to find the smaller
// candidate to replace the parent
if childIdx + 1 < n && h[childIdx].Compare(h[childIdx + 1]) * inverse > 0 {
childIdx += 1 // second child wins.
}
// is the re-inserted item smaller than the child? invariant achieved!
if v.Compare(h[childIdx]) * inverse < 0 {
break
}
// otherwise, swap and continue down the tree
h[idx] = h[childIdx]
idx = childIdx
}
// finally, put the re-inserted item in the right place
h[idx] = v
// slice the heap to remove the excessive last node that we've re-inserted
*hptr = h[:len(h)-1]
// return the pop'ed value
return root
}
// MinHeap is the exposed heap wrapper that implements the MinHeap invariant
type MinHeap heap
func (hptr *MinHeap) Push(i Comparer) {
h := heap(*hptr)
h.Push(i, 1)
*hptr = MinHeap(h)
}
func (hptr *MinHeap) Pop() Comparer {
h := heap(*hptr)
v := h.Pop(1)
*hptr = MinHeap(h)
return v
}
// MinHeap is the exposed heap wrapper that implements the MaxHeap invariant
type MaxHeap heap
func (hptr *MaxHeap) Push(i Comparer) {
h := heap(*hptr)
h.Push(i, -1)
*hptr = MaxHeap(h)
}
func (hptr *MaxHeap) Pop() Comparer {
h := heap(*hptr)
v := h.Pop(-1)
*hptr = MaxHeap(h)
return v
}
// that's unnecessary. the idea is to "hide away" the caveat of having
// to use make() to create heaps. it hides away the implementation detail of
// using a slice as the underlying heap representation. the client only cares
// about getting an object that satistifies the MinHeap API: Push() and Pop()
func NewMinHeap() MinHeap {
return make(MinHeap, 0)
}
func NewMaxHeap() MaxHeap {
return make(MaxHeap, 0)
}
// -------- test and play around
//
//
func main() {
// min heap
min := NewMinHeap()
min.Push(Int(5))
min.Push(Int(18))
min.Push(Int(2))
min.Push(Int(7))
fmt.Println("MinHeap=", min)
for {
i := min.Pop()
if i == nil {
break
}
fmt.Println("Pop()=", i)
}
// max heap
max := NewMaxHeap()
max.Push(Int(5))
max.Push(Int(18))
max.Push(Int(2))
max.Push(Int(7))
fmt.Println("MaxHeap=", max)
for {
i := max.Pop()
if i == nil {
break
}
fmt.Println("Pop()=", i)
}
}
// alias to int that implements the Comparer interface in order to make it
// sortable by MinHeap and MaxHeap. Construct similar compare function for every
// type to be sorted
type Int int
func (a Int) Compare(b Comparer) int {
bint := b.(Int)
if a < bint {
return -1
} else if a == bint {
return 0
} else {
return 1
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.