Я работаю с IntHeap exmaple из Пакетная куча . Каждая вещь выглядит очень просто для minHEAP. Посмотрите, как получить минимальное значение: нам просто нужно значение (*h)[0]. И так же, как в описании кучи, корневой узел возвращает минимальное значение
fmt.Printf("minimum: %d\n", (*h)[0]) // It will returns 1
Странные вещи начинаются с метода Pop(). В этом случае минимальное значение сохраняется в конце массива. x := old[n-1]. Но на 2 строки выше я получаю одинаковое минимальное значение по индексу 0.
Хм ... это очень интересно. Как получилось, что Go представляет собой обращенный массив для метода Pop? Любопытно, и необычно, и необычно, чтобы представить различный порядок массива в разных методах.
Я добавил две строки в пример, и да, Go передал обратный массив в метод Pop:
fmt.Println("In Pop",*h) // In Pop [2 3 5 1]
fmt.Println("In Main",*h) // In Main [1 2 5 3]
- Почему нам нужно каждый раз переворачивать массив?
- Требует ли он O (n) при каждом вызове 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{} {
fmt.Println("In Pop",*h) // In Pop [2 3 5 1]
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
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])
fmt.Println("In Main",*h) // In Main [1 2 5 3]
for h.Len() > 0 {
fmt.Printf("%d ", heap.Pop(h))
}
}
и вывод
minimum: 1
In Main [1 2 5 3]
In Pop [2 3 5 1]
1 In Pop [3 5 2]
2 In Pop [5 3]
3 In Pop [5]
5