堆索引示例说明

Question

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 min-heap 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[n-1]
    *h = old[0 : n-1]
    fmt.Printf("n: %v
", n)
    fmt.Printf("x: %v
", 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
", (*h)[0])
    for h.Len() > 0 {
        fmt.Printf("roll: %d
", (*h)[0])
        fmt.Printf("%d
", 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

Answer 1

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 all n in bounds), except that the root is wrong, in O(lg n) time. When you heap.Pop() an item, it almost certainly (*IntHeap).Swaps the first and last elements, does some more swapping to maintain the heap invariants, and then (*IntHeap).Pops 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 slice s int[] = (a, len=4, cap=4), then:

1. If len(s) == 1, stop.
2. Swap s[0] and s[len(s)-1].
3. Shrink the slice by one item: s = (array(s), len=len(s)-1, cap=cap(s)).
4. If the heap is out of order, fix it.
5. Go to 1.

Say your example starts with [1, 2, 5, 3]. Then:

[1, 2, 5, 3]
[3, 2, 5, 1]  Swap first and last
[3, 2, 5], 1  Shrink slice by one
[2, 3, 5], 1  Correct heap invariant
[5, 3, 2], 1  Swap first and last
[5, 3], 2, 1  Shrink slice by one
[3, 5], 2, 1  Correct heap invariant
[5, 3], 2, 1  Swap first and last
[5], 3, 2, 1  Shrink slice by one
  5, 3, 2, 1  Sorted (descending order)