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.

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.

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.

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

Done.

@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).

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

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

@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?

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).

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.

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

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

another possibility:

type Heap[E any] struct {
    Slice []E
    Less func(E, E) bool
}

I'm generally in favor of exporting Less from the struct, as it allows to avoid a pointer-indirection if the heap is used as a struct field.

Furthermore, one advantage of the original Lesser[E] variant would then also be that the extra func field doesn't have to be dragged around, making the type smaller. I do agree with @ianlancetaylor that the func version is more helpful in practice, but I think this drawback should be mentioned. It doesn't matter much as long as Heap can only be used as a pointer, though.

Placed on hold.
— rsc for the proposal review group

Over at #47619 (comment) @anacrolix asked about a concrete implementation of a generic slice-based heap. In my original proposal here, I linked to a very quick'n'dirty one in the playground (that simply wraps container/heap's current interface), but it would be interesting to do a proper implementation and compare some benchmarks to see how the type-parameterized version compares to the heap.Interface one. I might get around to that at some point but if someone else wants to write it up, feel free.

I linked to a very quick'n'dirty one in the playground (that simply wraps container/heap's current interface), but it would be interesting to do a proper implementation and compare some benchmarks to see how the type-parameterized version compares to the heap.Interface one.

If you do that, please measure the code segment size too. I'm curious to know how much expansion to expect from multiple instantiations of a generic type.

In C++ it was occasionally worth defining a widely used template as a mere wrapper around an untyped generic implementation, to reduce the quantity of code duplicated for each new template instantiation. The GNU linker was smart enough to coalesce templates that were essentially identical (e.g. vector of X* vs Y*). I don't know what the Go toolchain's notion of equivalence is, and presumably it varies across implementations.

It may be a bit awkward to have Pop and Peek to panic if heap is empty, since now caller needs to always keep track of the number of elements in the heap. Maybe, use the ok bool instead:

func (h *Heap[E]) Pop() (E, bool)
func (h *Heap[E]) Peek() (E, bool)

Google's generic BTree implementation uses this approach.

As for the any vs Ordered, I think there can be separate constructors, one wrapping another. Again, BTree has both New and NewOrdered. Not too pretty, but may save some boilerplate for tests and trivial types.

PS. @rsc, since 1.18 is long out, maybe this issue can be unheld?

@SaveTheRbtz I don't think you have to keep track. You only have to call h.Len to find out. Personally, I don't understand the decision of that API. After all, we don't require a two-variable assignment when accessing a slice, but trust programmers to check if len(s) > 0 first. I would personally prefer if h.Pop() was an expression I could put into a function call - almost every case where I used a heap in the past has been in a for h.Len() > 0 loop anyways.

It may be a bit awkward to have Pop and Peek to panic if heap is empty, since now caller needs to always keep track of the number of elements in the heap.

Well, not exactly "keep track"; they just need to call Len.

With the proposed signature, typical Heap-using code looks like this:

for h.Len() > 0 {
	e := h.Pop()
	// ...
}

With the boolean result, the loop looks like:

for {
	e, ok := h.Pop()
	if !ok {
		break
	}
	// ...
}

This particular case doesn't seem like much of an improvement.

I'm sympathetic to the notion that (E, bool) is a bit safer since it better encourages the caller to be aware of the empty case. OTOH the existing heap API doesn't provide the bool. On balance I prefer without the bool.

If you do that, please measure the code segment size too. I'm curious to know how much expansion to expect from multiple instantiations of a generic type.

@adonovan :

I had a need to play around with this, so I did an implementation and wrote some code generation to compare generic types which you can see here: https://go.dev/play/p/aQWbwOAnfXI

attached is resultant generated source code and the output of go tool nm -size -sort size -type for each binary. I was somewhat pleasantly surprised, though it's possible I'm doing something wrong.

cmdgen_main.go.txt
heapgeneric_nm_complete.txt
heapgeneric_nm_gheap_types.txt
heapstd_nm_complete.txt
heapstd_nm_heap_types.txt
main_generic.go.txt
main_std.go.txt
gheap.go.txt

A) This proposal can probably come off of hold now.

B) I would like to see this implemented as container/heap/v2 with this api:

package heap

func New[E any](cmp func(E, E) int) *Heap[E]  // Instead of a less function
func (h *Heap[E]) All() iter.Seq2[int, E] // No Slice() method

// Other methods as proposed above.

I have been using this form: https://github.com/anacrolix/generics/blob/main/heap/slice.go#L46-L51. It tries to avoid the heap allocation of Heap in func New[E any](cmp func(E, E) int) *Heap[E] above. It also lets the caller maintain ownership over the slice. In my use case I have a slice that moves around parts of the program, and at one point needs to be heapified, which I do by wrapping it in Interface[T] and passing that to the heap functions. I still maintain ownership afterwards and return to reuse it elsewhere in the program. Also note the rest of github.com/anacrolix/generics/heap is just a direct translation of container/heap to generics. I use this in a very performance critical part of anacrolix/torrent.

That's interesting. One idea would be to add heap.Slice[E any] to heap v1 and keep using the old interface functions, and also add a new heap v2 package that hides the slice and does its own memory management.

I suggest changing the proposed implementation of the Pop() function on sliceHeap:

func (s *sliceHeap[E]) Pop() interface{} {
	var zero E
	e := s.s[len(s.s)-1]
	if s.setIndex != nil {
		s.setIndex(e, -1)
	}
	// avoid memory leak by clearing out popped value in slice
	s.s[len(s.s)-1] = zero
	s.s = s.s[:len(s.s)-1]
	return e
}

s.s[len(s.s)-1] = zero will avoid retaining a reference to the popped value in the slice