为何在 heap.Pop 中要使用逆序数组？

怎么入门Golang编程？需要学习哪些知识点？这是新手们刚接触编程时常见的问题；下面golang学习网就来给大家整理分享一些知识点，希望能够给初学者一些帮助。本篇文章就来介绍《为何在 heap.Pop 中要使用逆序数组？》，涉及到，有需要的可以收藏一下

我正在使用 package heap 中的 intheap exmaple。对于 minheap 来说，一切看起来都非常简单。看看如何获​​得最小值：我们只需要 (*h)[0] 值。就像堆的描述一样，根节点返回最小值

fmt.printf("minimum: %d\n", (*h)[0]) // it will returns 1

奇怪的事情始于 pop() 方法。在这种情况下，最小值存储在数组的末尾。 x := 旧[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

解决方案

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

然后，当您 Pop 时，每个 Pop 仅需要 O(log n)。执行 init 对于确保我们可以弹出 O(log n) 至关重要。

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

Pop 所做的不是逆转。它：

1. 将最小元素（位于 [0]）与底层切片中的最后一个元素交换。现在最小元素位于最末尾，而元素 [0] 位于堆中“错误”的位置。
2. 使用 down 原语将新元素 [0] 移动到堆中的正确位置。这会重新调整堆的一些元素 - 但这不是回归。
3. 删除并返回元素 [n-1]，它是第 1 步中的原始最小元素。

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

1. 将根元素与最后一个元素交换。
2. 删除 lest 元素
3. 堆砌结构。

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

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

今天关于《为何在 heap.Pop 中要使用逆序数组？》的内容就介绍到这里了，是不是学起来一目了然！想要了解更多关于的内容请关注golang学习网公众号！