Heapsort implementation in Go

Question

I'm trying to implement code from Sedgewick's Algorithms textbook. The idea is to implement heapsort with the root of the heap stored in position 1 in the array.

Given the input S O R T E X A M P L E I expect a sorted output of A E E L M O P R S T X.

I'm having a bit of trouble implementing this, even when directly trying to translate the referenced Java code. This is what I have so far, which returns the following output:

package main

import (
    "bufio"
    "fmt"
    "os"
    "reflect"
    "strings"
)

type Heap struct {
    PQ []interface{}
}

func (h *Heap) Sort(pq []interface{}) {
    n := len(pq)

    for k := n / 2; k >= 1; k-- {
        Sink(pq, k, n)
    }
    for n > 1 {
        Exchange(pq, 1, n)
        n = n - 1
        Sink(pq, 1, n)
    }
}

func Sink(pq []interface{}, k, n int) {
    fmt.Println(k, n, pq)
    for 2*k <= n {
        j := 2 * k
        if j < n && Less(pq, j, j+1) {
            j = j + 1
        }
        Exchange(pq, k, j)
        k = j
    }
}

func Exchange(pq []interface{}, j, k int) {
    curr := pq[j-1]
    pq[j-1] = pq[k-1]
    pq[k-1] = curr
}

func Less(pq []interface{}, j, k int) bool {
    x, y := pq[j-1], pq[k-1]
    if reflect.TypeOf(x) != reflect.TypeOf(y) {
        fmt.Println("mismatched inputs", x, y)
        panic("mismatched inputs")
    }
    switch x.(type) {
    case int:
        a, b := x.(int), y.(int)
        if a > b {
            return false
        }
    case float32:
        a, b := x.(int), y.(int)
        if a > b {
            return false
        }
    case float64:
        a, b := x.(int), y.(int)
        if a > b {
            return false
        }
    case string:
        a, b := x.(string), y.(string)
        if a > b {
            return false
        }
    default:
        panic("unhandled types, please add case.")
    }
    return true
}

func main() {
    a := readStdin()
    var h *Heap = new(Heap)
    h.PQ = a
    h.Sort(h.PQ)
    fmt.Println(h.PQ)
}

func readStdin() []interface{} {
    scanner := bufio.NewScanner(os.Stdin)
    var items []interface{}
    for scanner.Scan() {
        item := scanner.Text()
        tmp := strings.SplitAfter(item, " ")
        items = make([]interface{}, len(tmp)+1)
        for i, item := range tmp {
            items[i+1] = item
        }
    }
    if err := scanner.Err(); err != nil {
        panic(err)
    }
    return items
}

mismatched inputs E 
panic: mismatched inputs

which panics as expected because of the comparison between nil value at index 0 and the currents slice value from 1..n. Perhaps I'm looking at this problem a bit too closely, or more than likely, I am missing a key point in the heapsort implementation altogether. Thoughts?

user_1400793 · Answer

The standard library contains a heap package that you can use to directly implement this.

Even if you want to re-implement it yourself, the idea of using an interface to access the underlying slice is a good one -- allowing you to focus on the abstract heap operations without the mess of dealing with various types.

Here's a complete working example of heapsort, running on a slice of runes. Note that *runeSlice type implements heap.Interface by defining the three methods of sort.Interface: Len, Less, Swap, and the additional two methods from heap.Interface: Push and Pop.

package main

import (
    "container/heap"
    "fmt"
)

type runeSlice []rune

func (r runeSlice) Len() int           { return len(r) }
func (r runeSlice) Less(i, j int) bool { return r[i] > r[j] }
func (r runeSlice) Swap(i, j int)      { r[i], r[j] = r[j], r[i] }

func (r *runeSlice) Push(x interface{}) {
    *r = append(*r, x.(rune))
}

func (r *runeSlice) Pop() interface{} {
    x := (*r)[len(*r)-1]
    *r = (*r)[:len(*r)-1]
    return x
}

func main() {
    a := []rune("SORTEXAMPLE")
    h := runeSlice(a)
    heap.Init(&h)
    for i := len(a) - 1; i >= 0; i-- {
        a[0], a[i] = a[i], a[0]
        h = h[:i]
        heap.Fix(&h, 0)
    }
    fmt.Println(string(a))
}

Heapsort implementation in Go

1 Answers