时间戳

首页 > 解决方案 > 堆索引示例说明

sorting - 堆索引示例说明

问题描述

此代码取自 Go heap 示例（我自己添加了打印）。这里是游乐场。 https://play.golang.org/p/E69SfBIZF5X

大多数事情都是直截了当且有意义的，但我无法解决的一件事是为什么index 0堆中的“最小”打印main()返回值1（正确的最小值）但在堆的 pop 函数中打印 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

标签： sortinggodata-structuresheap

解决方案

教科书的堆算法包括一种修复堆的方法，如果你知道整个堆结构是正确的（a[n] < a[2*n+1] && a[n] < a[2*n+2]，对于所有n边界），除了根是错误的，在 O(lg n ) 时间内。当您heap.Pop()使用一个项目时，它几乎可以肯定(*IntHeap).Swap是第一个和最后一个元素，进行更多交换以维护堆不变量，然后(*IntHeap).Pop是最后一个元素。这就是你在这里看到的。

您也可以使用它来实现堆排序。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)

推荐阅读