为什么 heap.Pop 使用倒置数组？

Question

我正在使用来自 Package Heap 的 IntHeap 示例。对于 minHEAP，每件事看起来都非常简单。看看如何获得最小值：我们只需要 (*h)[0] 值。又如heap描述中的根节点returns最小值

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]

为什么每次都需要反转数组？
每次 Pop 调用都需要 O(n) 吗？

这是一个完整的例子，有两个变化：

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

Answer 1

当您使用 Init 从切片初始化堆时，它会通过重新排列切片来建立堆不变量。此操作是 O(n) 并且仅在初始化时发生一次，而不是在每次弹出时发生！

那么，当你Pop时，每个Pop只需要O(log n)。执行初始化对于确保我们可以弹出 O(log n).

至关重要

了解有关堆的更多信息 on Wikipedia. The article on Heapsort 具有 heapify 操作的伪代码，由 heap.Init)

执行

Pop做的不是逆向。它：

将最小元素（位于 [0]）与底层切片中的最后一个元素交换。现在最小的元素在最后，元素[0]在堆中"wrong"的地方。
使用 down 原语将新元素 [0] 移动到堆中的正确位置。这会重新排列堆的一些元素 - 但它不是反转。
删除 returns 元素 [n-1]，这是第 1 步中的原始最小元素。

Answer 2

这不是倒车。这是一种从 MinHeap 中删除最小元素的算法。

将根元素与最后一个元素交换。
移除 less 元素
堆化结构。

在当前情况下，包委托给开发人员步骤 #2。并为除最后一个元素之外的所有堆实现步骤#1 和步骤#3。

https://youtu.be/WCm3TqScBM8?t=391

为什么 heap.Pop 使用倒置数组？

Why do the heap.Pop wields with reversed array?

arrays

heap

go