proposal: container/heap: add Heap, a heap backed by a slice

[cespare]

This proposal is for use with #43651. I propose to add a parameterized Heap type to the container/heap package. For the typical usage of container/heap where the heap is backed by a slice, using heap.Heap is safer, more convenient, and more readable:

• No conversions to or from any are required.
• Instead of defining 5 methods (Less, Len, Swap, Push, and Pop), most of which are typically boilerplate, only the cmp function is needed.
• Having the heap functions Push, Pop, etc. be methods is more natural than functions: pq.Push(e) vs. heap.Push(pq, e).

Update 2024-07-22: Switched from a less function to a cmp function.

Update 2021-08-28: Removed the Lesser interface; pass in a less function to the constructor.

// A Heap is a min-heap backed by a slice.
type Heap[E any] struct { ... }

// New constructs a new Heap with a comparison function.
func New[E any](less func(E, E) bool) *Heap[E]

// Push pushes an element onto the heap. The complexity is O(log n)
// where n = h.Len().
func (h *Heap[E]) Push(elem E)

// Pop removes and returns the minimum element (according to the less function)
// from the heap. Pop panics if the heap is empty.
// The complexity is O(log n) where n = h.Len().
func (h *Heap[E]) Pop() E

// Peek returns the minimum element (according to the less function) in the heap.
// Peek panics if the heap is empty.
// The complexity is O(1).
func (h *Heap[E]) Peek() E

// Len returns the number of elements in the heap.
func (h *Heap[E]) Len() int

// Slice returns the underlying slice.
// The slice is in heap order; the minimum value is at index 0.
// The heap retains the returned slice, so altering the slice may break
// the invariants and invalidate the heap.
func (h *Heap[E]) Slice() []E

// SetIndex specifies an optional function to be called
// when updating the position of any heap element within the slice,
// including during the element's initial Push.
//
// SetIndex must be called at most once, before any calls to Push.
//
// When an element is removed from the heap by Pop or Remove,
// the index function is called with the invalid index -1
// to signify that the element is no longer within the slice.
func (h *Heap[E]) SetIndex(f func(E, int))

// Fix re-establishes the heap ordering
// after the element at index i has changed its value.
// Changing the value of the element at index i and then calling Fix
// is equivalent to, but less expensive than,
// calling h.Remove(i) followed by a Push of the new value.
// The complexity is O(log n) where n = h.Len().
// The index for use with Fix is recorded using the function passed to SetIndex.
func (h *Heap[E]) Fix(i int)

// Remove removes and returns the element at index i from the heap.
// The complexity is O(log n) where n = h.Len().
// The index for use with Remove is recorded using the function passed to SetIndex.
func (h *Heap[E]) Remove(i int) E

Notes

I evaluated the uses of container/heap in our company's internal code as well as my own projects and found that all of them used a heap backed by a slice. This indicates that a slice-based implementation could save a good deal of boilerplate in much the same way that sort.Slice saves boilerplate over sort.Sort.

A simpler API would do away with the "slice"-ness, leaving the implementation unspecified and removing the index-based methods:

type Heap[E any] struct { ... }

func NewHeap[E any](less func(E, E) bool) *Heap[E]
func (h *Heap[E]) Push(elem E)
func (h *Heap[E]) Pop() E
func (h *Heap[E]) Peek() E
func (h *Heap[E]) Len() int

However, my review of container/heap usage showed that this simplified Heap would cover fewer than half of those real-life use cases. Many real uses of container/heap need the index-based methods Fix or Remove; for instance, to delete items from a priority queue.

A different simplification would be to use constraints.Ordered elements rather than the Lesser constraint. While this makes for concise example code, in practice, such heaps seem relatively rare; all the uses I analyzed had slice elements of some compound type.

---

Here is a playground implementation of the proposal showing the priority queue example implemented using Heap.

[rsc]

I'm worried about doing too much in the standard library in Go 1.18.
We don't really know what best practices for containers are going to be.
I'm wary of committing to a container/set API as well as to committing to this API.

[ianlancetaylor]

type Lesser[E any] interface {
	Less(E) bool
}

type Heap[E Lesser[E]] struct { ... }

I don't think this is going to be the right path for generic data types. I think it is better to initialize the heap with a comparison function. My argument is that if you have a comparison function, it's tedious to create a type with a Less method that invokes that comparison function. But if you have a Less method, it's trivial to use it as a comparison function, by simply passing elementType.Less.

I admit that this means that the zero value can't be used directly. Still, I think that overall it is the more flexible approach.

[ianlancetaylor]

The docs should mention what happens for Pop and Peek if the heap is empty.

I'm not quite seeing what SetIndex is for. At first I thought it could be used to maintain a secondary data structure, but in that case I think it needs the index when an element is removed.

[cespare]

The docs should mention what happens for Pop and Peek if the heap is empty.

Done.

[cespare]

@ianlancetaylor

I'm not quite seeing what SetIndex is for. At first I thought it could be used to maintain a secondary data structure,

The playground example I linked is an adapted version of the PriorityQueue example from the container/heap package which makes use of SetIndex.

In general, I would expect it to be used to associate each element with its index somehow, whether that's as part of the element (as in my example) or using some secondary data structure such as a map[E]int.

but in that case I think it needs the index when an element is removed.

I don't follow this. SetIndex is called when an element's index is changed; the index provided to the callback is the new index (so -1 when the element is removed); it sounds like you're saying we would need the old index (instead? in addition?). I don't see why, though -- for example, if your external data structure is a map[E]int, then when the callback is called with f(e, -1), the code would delete(m, e).

[ianlancetaylor]

If the secondary data structure is another slice, then, you're right, we need both the old and the new index.

[rsc]

This proposal has been added to the active column of the proposals project
and will now be reviewed at the weekly proposal review meetings.
— rsc for the proposal review group

[cespare]

@ianlancetaylor yes, an auxiliary parallel slice that mirrors all the swaps of the Heap slice is a situation in which it would be convenient to have the old index as well.

I'm not sure why you'd ever want to maintain a parallel slice, though. If you have some extra data to associate with each heap element, why not add it to the element itself?

[cespare]

I don't think this is going to be the right path for generic data types. I think it is better to initialize the heap with a comparison function.

OK, after some thought, I agree that this will make many use cases simpler. I updated the proposal to use a less comparison function passed to a constructor (New).

[kylelemons]

I'm also in favor of less being a function passed into the constructor. In my usages, I often use heap with a local type (inside the function) which cannot have a method. The reverse is possible: a type with a less method can pass the method value to the constructor.

[rsc]

It sounds like we should put this on hold for after Go 1.18. Any objections to that?