1package main
  2
  3import (
  4  "container/heap"
  5  "fmt"
  6)
  7
  8// create type myHeap, based on []int
  9type myHeap []int
 10
 11// heap.Interface requires that myHeap
 12// implement the three methods from
 13// sort.Interface, plus Push and Pop
 14// (below). Here we are creating a max
 15// heap, so we do m[i] > m[j]. We'd do
 16// m[i] < m[j] if we were creating a min
 17// heap. As you'll see in the heapsort
 18// method, a max heap sorts low -> high
 19// values.
 20func (m myHeap) Less(i, j int) bool {
 21  return m[i] > m[j]
 22}
 23
 24func (m myHeap) Swap(i, j int) {
 25  m[i], m[j] = m[j], m[i]
 26}
 27
 28func (m myHeap) Len() int {
 29  return len(m)
 30}
 31
 32// Push requires a pointer receiver because
 33// append may allocate a new backing array,
 34// changing the slice header. A value receiver
 35// would leave the caller's header unchanged.
 36func (m *myHeap) Push(x interface{}) {
 37  *m = append(*m, x.(int))
 38}
 39
 40// Pop requires a pointer receiver because we
 41// shorten the slice (reduce len by 1). A
 42// value receiver would only shorten the
 43// local copy — the caller's slice header
 44// would be unchanged.
 45func (m *myHeap) Pop() interface{} {
 46  old := *m
 47  n := len(old)
 48  x := old[n-1]
 49  *m = old[:n-1]
 50  return x
 51}
 52
 53// We mutate the array the slice points to in-place.
 54// The slice header (pointer/len/cap) is copied when
 55// assigned, but the backing array is shared.
 56func heapsort(sl []int) {
 57  // copies the slice header; h and sl
 58  // share the same backing array
 59  h := myHeap(sl)
 60
 61  // heap.Init operates in-place on the slice
 62  // (no array copy) to build a heap.
 63  // note we pass &h not &sl
 64  // because h is the myHeap type that implements heap.Interface
 65  // sl is []int which does not implement heap.Interface
 66  heap.Init(&h)
 67  // Now h and sl are distinct slice headers that
 68  // refer to the same array.
 69  for i := len(sl) - 1; i >= 0; i-- {
 70    // heap.Pop swaps the root with the last element,
 71    // shortens the active heap, and returns the removed
 72    // root (the current max). That max already sits
 73    // at the rightmost position, so assigning
 74    // sl[i] = heap.Pop(&h).(int)
 75    // writes into a slot no longer needed by the active heap.
 76    sl[i] = heap.Pop(&h).(int)
 77  }
 78}
 79
 80func main() {
 81  input := []int{5, 1, 2, 7}
 82  h := myHeap{}
 83  heap.Init(&h)
 84  for _, n := range input {
 85    heap.Push(&h, n)
 86  }
 87  fmt.Println(h)
 88  // [7 5 2 1]
 89  heap.Push(&h, 3)
 90  el := heap.Pop(&h)
 91  fmt.Println(el)
 92  // 7
 93  heap.Push(&h, 10)
 94  el = heap.Pop(&h)
 95  fmt.Println(el)
 96  // 10
 97  heapsort(h)
 98  fmt.Println(h)
 99  // [1 2 3 5]
100}