I have implemented a binary heap in Go to get familiar with the language.
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.
