Skip to content

Instantly share code, notes, and snippets.

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

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 ab. */ 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 } }
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.