Explanation of heap indexing example
This code is taken from the Go heap example (with my own added prints). Here's the playground. https://play.golang.org/p/E69SfBIZF5X
Most everything is straightforward and makes sense, but the one thing I can't wrap around is why the 'minimum' print on index 0
of the heap in main()
returns the value 1
(the correct minimum) but printing 4 in the heap's pop function returns 1
(see output).
If the root (minimum) of a heap is always at n=0
, why is it n=4
in the pop function itself? It then seems to work fine, in descending order.
Can someone explain what's going on here? I don't feel comfortable implementing something like the Pop before I understand what's going on.
// This example demonstrates an integer heap built using the heap interface.
package main
import (
"container/heap"
"fmt"
)
// An IntHeap is a minheap of ints.
type IntHeap []int
func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) {
// Push and Pop use pointer receivers because they modify the slice's length,
// not just its contents.
*h = append(*h, x.(int))
}
func (h *IntHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n1]
*h = old[0 : n1]
fmt.Printf("n: %v\n", n)
fmt.Printf("x: %v\n", x)
return x
}
// This example inserts several ints into an IntHeap, checks the minimum,
// and removes them in order of priority.
func main() {
h := &IntHeap{2, 1, 5}
heap.Init(h)
heap.Push(h, 3)
fmt.Printf("minimum: %d\n", (*h)[0])
for h.Len() > 0 {
fmt.Printf("roll: %d\n", (*h)[0])
fmt.Printf("%d\n", heap.Pop(h))
}
}

Output
x = value
n = index
minimum: 1
roll: 1
n: 4
x: 1
1
roll: 2
n: 3
x: 2
2
roll: 3
n: 2
x: 3
3
roll: 5
n: 1
x: 5
5
aroooo ask on
1 Answers Explanation of heap indexing example
The textbook heap algorithms include a way to fix up a heap if you know the entire heap structure is correct (
a[n] < a[2*n+1] && a[n] < a[2*n+2]
, for alln
in bounds), except that the root is wrong, in O(lg n) time. When youheap.Pop()
an item, it almost certainly(*IntHeap).Swap
s the first and last elements, does some more swapping to maintain the heap invariants, and then(*IntHeap).Pop
s the last element. That's what you're seeing here.You can also use this to implement a heap sort. Say you have an array
int[4]
you're trying to sort. Take a slices int[] = (a, len=4, cap=4)
, then:len(s) == 1
, stop.s[0]
ands[len(s)1]
.s = (array(s), len=len(s)1, cap=cap(s))
.Say your example starts with [1, 2, 5, 3]. Then:
David Maze 4 months ago