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]I Produceの配列について[16 14 9 10 8 1 4 2 3 7]

9 は 1 レベル高すぎて、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 の左の子を返します。それぞれに 1 つ追加するだけです。

0 の代わりにheapSort呼び出す同様の問題がありました。h.MaxHeapify(1)

動作するコードの修正版を次に示します (とを使用testing/quickして検証するためのテスト ファイルも含まれています)。container/heapsort

heap.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 に答える