Объяснение примера индексации кучи

Question

Этот код взят из примера кучи Go (с моими добавленными отпечатками). Вот детская площадка. https://play.golang.org/p/E69SfBIZF5X

В большинстве случаев все просто и понятно, но одну вещь, которую я не могу обернуть, это то, почему «минимальная» печать на index 0 кучи в main() возвращает значение 1 (правильный минимум) но печать 4 в поп-функции кучи возвращает 1 (см. вывод).

Если корень (минимум) кучи всегда равен n=0, почему он n=4 в самой функции pop? Затем, кажется, работает нормально, в порядке убывания.

Может кто-нибудь объяснить, что здесь происходит? Я не чувствую себя комфортно, внедряя что-то наподобие Pop, пока не понял, что происходит.

// 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", 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

Answer 1

Алгоритмы кучи учебника включают способ исправления кучи, если вы знаете, что вся структура кучи правильная (a[n] < a[2*n+1] && a[n] < a[2*n+2], для всех n в границах), за исключением того, что корень неправильный, в O (lg *) 1003 * n ) время. Когда вы heap.Pop() элемент, он почти наверняка (*IntHeap).Swap s первый и последний элементы, делает еще один обмен, чтобы сохранить инварианты кучи, а затем (*IntHeap).Pop s элемент last . Это то, что вы видите здесь.

Вы также можете использовать это для реализации сортировки кучи . Скажем, у вас есть массив int[4], который вы пытаетесь отсортировать. Возьмите кусочек s int[] = (a, len=4, cap=4), затем:

1. Если len(s) == 1, остановитесь.
2. Своп s[0] и s[len(s)-1].
3. Уменьшите ломтик на один элемент: s = (array(s), len=len(s)-1, cap=cap(s)).
4. Если куча вышла из строя, исправьте ее.
5. Перейти к 1.

Скажем, ваш пример начинается с [1, 2, 5, 3]. Тогда:

[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)