1
\$\begingroup\$

I have implemented a binary heap in Go to get familiar with the language.

GitHub

package heap

import (
    "sync"
)

type Item interface {
    Less(than Item) bool
}

type Heap struct {
    sync.Mutex
    data []Item
    min  bool
}

func New() *Heap {
    return &Heap{
        data: make([]Item, 0),
    }
}

func NewMin() *Heap {
    return &Heap{
        data: make([]Item, 0),
        min:  true,
    }
}

func NewMax() *Heap {
    return &Heap{
        data: make([]Item, 0),
        min:  false,
    }
}

func (h *Heap) isEmpty() bool {
    return len(h.data) == 0
}

func (h *Heap) Len() int {
    return len(h.data)
}

func (h *Heap) Get(n int) Item {
    return h.data[n]
}

func (h *Heap) Insert(n Item) {
    h.Lock()
    defer h.Unlock()

    h.data = append(h.data, n)
    h.siftUp()

    return
}

func (h *Heap) Extract() (el Item) {
    h.Lock()
    defer h.Unlock()
    if h.Len() == 0 {
        return
    }

    el = h.data[0]
    last := h.data[h.Len()-1]
    if h.Len() == 1 {
        h.data = nil
        return
    }

    h.data = append([]Item{last}, h.data[1:h.Len()-1]...)
    h.siftDown()

    return
}

func (h *Heap) siftUp() {
    for i, parent := h.Len()-1, h.Len()-1; i > 0; i = parent {
        parent = i >> 1
        if h.Less(h.Get(i), h.Get(parent)) {
            h.data[parent], h.data[i] = h.data[i], h.data[parent]
        } else {
            break
        }
    }
}

func (h *Heap) siftDown() {
    for i, child := 0, 1; i < h.Len() && i<<1+1 < h.Len(); i = child {
        child = i<<1 + 1

        if child+1 <= h.Len()-1 && h.Less(h.Get(child+1), h.Get(child)) {
            child++
        }

        if h.Less(h.Get(i), h.Get(child)) {
            break
        }

        h.data[i], h.data[child] = h.data[child], h.data[i]
    }
}

func (h *Heap) Less(a, b Item) bool {
    if h.min {
        return a.Less(b)
    } else {
        return b.Less(a)
    }
}

It works fine and my tests pass just fine. I have implemented a heap sort based on this.

However, my implementation of heapsort give very very very bad performances, even when benchmark against \$O(n^2)\$algorithms such as insertion short.

Here are my results for both heap and insertion sort on the same data sets:

BenchmarkHeapSort100       20000         95676 ns/op
BenchmarkHeapSort1000        500       3613389 ns/op
BenchmarkHeapSort10000         5     287265292 ns/op
BenchmarkHeapSort100000        1    37184383822 ns/op
ok      github.com/arnauddri/algorithms/algorithms/sorting/heap-sort    43.738s
PASS

BenchmarkInsertionSort100   10000000           228 ns/op
BenchmarkInsertionSort1000   1000000          1857 ns/op
BenchmarkInsertionSort10000   100000         18822 ns/op
BenchmarkInsertionSort100000           1    3949000733 ns/op
ok      github.com/arnauddri/algorithms/algorithms/sorting/insertion-sort   12.348s
PASS

I have reviewed my code but I struggle to see what leads to bad performances. I'd really appreciate it if someone had a piece of advice on how I can improve my data structure.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.