Repository: go
Issue: proposal: container/heap: add Heap, a heap backed by a slice
Labels: Proposal,generics

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`](https://github.com/golang/go/issues/45458) 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](https://go.dev/play/p/350YF5j23xY) of the proposal showing the priority queue example implemented using `Heap`.