proposal: container: Generic Array Heap Implementation

[chlovec]

Proposal Details

container/heap provides a heap interface allowing people to create there own implementation leading to duplication of efforts.

I am proposing a generic heap implementation that uses a slice as the internal data structure that everyone can use and save the effort them the effort of implementing a new one each time they need to use a heap.

The main APIs are:

type AHeap[T any] struct {
	Heap        []T
	LessFunc    func(a, b T) bool
}

// Constructor function
func New[T any](lessFunc func(a, b T)) *AHeap[T] 

// Converts a slice to a heap
// Call this function if heap is initialized with a slice that already contains elements or if heap elements where manually modified
// Time complexity is O(nlogn)
func (ah *AHeap[T]) BuildHeap()

// Returns the element at the top of the heap along with true
// Will return zeroValue of T and false if heap is empty
// Time complexity is O(1)
func (ah *AHeap[T]) Top() (T, bool)

// Removes and returns the top element of the heap along with true.
// Returns the zero value of T and false if the heap is empty.
// Time complexity is O(logn)
func (ah *AHeap[T]) Pop() (T, bool) 

// Pushes T onto the heap
// Time complexity is O(logn)
func (ah *AHeap[T]) Push(value T) 

[thepudds]

Does this overlap with #47632?

[chlovec]

Does this overlap with #47632?

There may be some overlap but my proposal seems to be cleaner and clearer.

[gabyhelp]

Related Issues

• proposal: container: Generic Binary Heap #73346
• proposal: container/heap: add Heap, a heap backed by a slice #47632
• proposal: container/heap generic example #61993 (closed)
• proposal: Go 2: #63406 (closed)
• container/heap: use sort.Interface where possible #65967

_{(Emoji vote if this was helpful or unhelpful; more detailed feedback welcome in this discussion.)}

[seankhliao]

please discuss this in #47632, there is a lot of overlap with what it calls the simpler API that doesn't cover sufficient existing use cases