Easy way to implement heaps in Go
Heap is one of the fundamental data structures that offer efficient operations such as O(1) lookup of the minimum or maximum element and O(log(n)) push and pop operations. Go offers a quick and easy way of implementing them, thanks to the streamlined process provided by the
container/heap
package. In this post, we'll explore the basics of heap implementation in Go and dive into some practical examples.
Implementation Basics
A
heap.Interface
defines the methods needed to use a type as a heap by this package. Here's how it's defined:
It extends the
sort.Interface
by adding
Push
and
Pop
methods for heap manipulation. Heap package does not use generics at this point, so values which will be pushed and popped are defined as
any
.
Let’s begin our exploration from implementing a minimum heap for integers and satisfying the
sort.Interface:
So far it’s pretty straightforward,
Len
just returns the lenght of the slice,
Swap
changes the values between two slice elements and
Less
defines how to compare them. Based on the
Less
definition, the heap can change it’s behaviour . If you’d rather look for
the biggest numbers
instead, you just need to change the
<
sign into
>
.
Having implemented the
sort.Interface
, it’s time to focus on functions which will be responsible for adding new elements and popping the smallest one:
Both functions use pointer receivers opposed to ones implemented earlier. It’s because
Push
and
Pop
modify not only the values but also the slice’s length.
Push
takes
v
and appends it to a dereferenced
h
after type asserting to
int
.
Pop
saves slice’s last element and decrements its size by slicing up to the last element.
That’s all it takes to implement a fully functional heap in Go, which can be used with
containter/heap
package!