GoLang Heap и Heapsort

Поэтому я пытаюсь реализовать максимальную кучу для практики, чтобы я мог познакомиться с 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.

Куда я иду не так?

Я также знаю, что-то странное, потому что, когда я пытаюсь и heapsort

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
}

Это не работает.

Источник

2 ответа

Решение

Проблема заключалась в том, что индексы срезов начинаются с нуля, поэтому ваш:

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

дает левому потомку 0 для индекса 0 (т. е. самого себя). Просто добавьте один к каждому из них.

Ваш heapSort была похожая проблема вызова h.MaxHeapify(1) вместо 0. Это фактически оставило то значение, которое было впереди.

Вот модифицированная версия вашего кода, которая работает (тестовый файл также включен, который использует testing/quick проверить это против container/heap а также sort).

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)
}

Детская площадка

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)
    }
}
Источник

Вот способ сделать то же самое без добавления структуры для хранения данных и размера кучи:

// 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)

}
Источник
Другие вопросы по тегам