algorithm - GoLang 堆和堆排序

Question

所以我正在尝试实现一个最大堆来练习，这样我就可以熟悉 Go。

type MaxHeap struct {
    slice []int
    heapSize int
}
func BuildMaxHeap(slice []int) MaxHeap{
    h := MaxHeap{slice: slice, heapSize: len(slice)}
    for i := len(slice)/2; i >= 0; i-- {
        h.MaxHeapify(i)
    }
    return h
}

func (h MaxHeap) MaxHeapify(i int) {
    left := 2*i
    right := 2*i + 1
    largest := i
    slice := h.slice

    if left < h.size() {
        if slice[left] > slice[i] {
            largest = left
        } else {
            largest = i
        }
    }
    if right < h.size() {
        if slice[right] > slice[largest] {
            largest = right
        }
    }
    if largest != i {
        prevLargest := slice[i]
        slice[i] = slice[largest]
        slice[largest] = prevLargest
        h.MaxHeapify(largest)
    }
}

在 [4,1,3,2,16,9,10,14,8,7] 数组上，我生成 [16 14 9 10 8 1 4 2 3 7]

这是错误的，因为 9 太高了一个级别，应该与 10 切换。

我哪里错了？

我也知道有些事情很奇怪，因为当我尝试堆排序时

func heapSort(slice []int) []int {
    h := BuildMaxHeap(slice)
    fmt.Println(slice)
    for i := len(h.slice) - 1; i >=1 ; i-- {
        first := h.slice[0]
        last := h.slice[i]
        h.slice[0] = last
        h.slice[i] = first
        h.heapSize--
        h.MaxHeapify(1)
    }
    return h.slice
}

它不起作用。

Answer 1

问题是 slice 索引从零开始，所以您:

left := 2*i
right := 2*i + 1

为索引 0(即它自己)给出一个 0 的左 child 。只需向其中每一个添加一个即可。

您的 heapSort 在调用 h.MaxHeapify(1) 而不是 0 时遇到了类似的问题。这有效地保留了前面的任何值。

这是您的代码的修改版本(还包括测试文件，它使用 testing/quick 根据 container/heap 和 sort< 对其进行验证)。

堆.go:

package main

import "fmt"

type MaxHeap struct {
    slice    []int
    heapSize int
}

func BuildMaxHeap(slice []int) MaxHeap {
    h := MaxHeap{slice: slice, heapSize: len(slice)}
    for i := len(slice) / 2; i >= 0; i-- {
        h.MaxHeapify(i)
    }
    return h
}

func (h MaxHeap) MaxHeapify(i int) {
    l, r := 2*i+1, 2*i+2
    max := i

    if l < h.size() && h.slice[l] > h.slice[max] {
        max = l
    }
    if r < h.size() && h.slice[r] > h.slice[max] {
        max = r
    }
    //log.Printf("MaxHeapify(%v): l,r=%v,%v; max=%v\t%v\n", i, l, r, max, h.slice)
    if max != i {
        h.slice[i], h.slice[max] = h.slice[max], h.slice[i]
        h.MaxHeapify(max)
    }
}

func (h MaxHeap) size() int { return h.heapSize } // ???

func heapSort(slice []int) []int {
    h := BuildMaxHeap(slice)
    //log.Println(slice)
    for i := len(h.slice) - 1; i >= 1; i-- {
        h.slice[0], h.slice[i] = h.slice[i], h.slice[0]
        h.heapSize--
        h.MaxHeapify(0)
    }
    return h.slice
}

func main() {
    s := []int{4, 1, 3, 2, 16, 9, 10, 14, 8, 7}
    h := BuildMaxHeap(s)
    fmt.Println(h)

    s = heapSort(s)
    fmt.Println(s)
}

Playground

heap_test.go:

package main

import (
    "container/heap"
    "reflect"
    "sort"
    "testing"
    "testing/quick"
)

// Compare against container/heap implementation:
// https://golang.org/pkg/container/heap/#example__intHeap

type IntHeap []int

func (h IntHeap) Len() int            { return len(h) }
func (h IntHeap) Less(i, j int) bool  { return h[i] > h[j] } // use > for MaxHeap
func (h IntHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func TestMaxHeap(t *testing.T) {
    f := func(s []int) bool {
        //t.Log("testing heap len", len(s))
        h := BuildMaxHeap(s)
        h2 := make(IntHeap, len(h.slice))
        copy(h2, h.slice)
        for i := range h2 {
            heap.Fix(&h2, i)
        }
        eq := reflect.DeepEqual(h.slice, []int(h2))
        if !eq {
            t.Logf("MaxHeap: %v\n\t IntHeap: %v", h.slice, h2)
        }
        return eq
    }
    if err := quick.Check(f, nil); err != nil {
        t.Error(err)
    }
}

func TestHeapSort(t *testing.T) {
    f := func(s []int) bool {
        s = heapSort(s)
        return sort.IntsAreSorted(s)
    }
    if err := quick.Check(f, nil); err != nil {
        t.Error(err)
    }
}