1

所以我正在尝试实现一个最大堆来练习，这样我就可以熟悉 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
}

这没用。

4

2 回答 2

8

问题是切片索引从零开始，所以你：

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

为索引 0（即自身）给出 0 的左孩子。只需在其中每一个中添加一个。

你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)
    }
}
于 2015-05-21T22:36:35.477 回答
0

这是一种无需添加结构来保存数据和堆大小的方法来做同样的事情：

// AS described in Introduction to Algorithms (3rd Edition)
package main

import (
    "fmt"
)

func left(i int) int {
    return 2 * i
}

func right(i int) int {
    return 2*i + 1
}

func parent(i int) int {
    return i / 2
}

func maxHeapify(a []int, i int) []int {

    fmt.Printf("Array: %v\n", a)

    l := left(i) + 1
    r := right(i) + 1
    var largest int
    if l < len(a) && l >= 0 && a[l] > a[i] {
        largest = l
    } else {
        largest = i
    }
    if r < len(a) && r >= 0 && a[r] > a[largest] {
        largest = r
    }
    if largest != i {
        fmt.Printf("Exchanging: %d index (%d) with %d index (%d)\n", a[i], i, a[largest], largest)
        a[i], a[largest] = a[largest], a[i]
        a = maxHeapify(a, largest)
    }
    return a
}

func buildMaxHeap(a []int) []int {
    for i := len(a)/2 - 1; i >= 0; i-- {
        fmt.Printf("Building: %d index %d\n", a[i], i)
        a = maxHeapify(a, i)
    }
    return a
}

func heapsort(a []int) []int {

    a = buildMaxHeap(a)
    fmt.Printf("Starting sort ... array is %v\n", a)
    size := len(a)
    for i := size - 1; i >= 1; i-- {
        a[0], a[i] = a[i], a[0]
        size--
        maxHeapify(a[:size], 0)
    }
    return a
}

func main() {

    a := [10]int{4, 1, 3, 2, 16, 9, 10, 14, 8, 7}
    fmt.Printf("Array: %v\n", a)

    b := heapsort(a[:])
    fmt.Printf("Array: %v\n", b)

}
于 2018-06-09T11:57:33.683 回答