proposal: container: Generic Binary Heap

[chlovec]

Proposal Details

I already have submitted a proposal for an array heap in #73345. However, there are situations such as in data stream and large data processing where array heaps will not work.

I am proposing a Binary Heap for handling of large data sets.

The APIs are:

type heapNode[T any] struct {
value T
height int
left *heapNode[T]
right *heapNode[T]
}

// Constructor function for the heapNode
func newHeapNode[T any](value T) *heapNode[T] {
return &heapNode[T]{value: value, size: 1, height: 1}
}

type BHeap[T any] struct {
lessFunc func(a, b T) bool
root *heapNode[T]
}

// Constructor function for the binary heap
func NewBHeap[T any](lessFunc func(a, b T) bool) *BHeap[T]

// Returns the value of the topmost node of the heap along with true
// This value is equivalent to the minimum or maximum value of all the values in the heap, depending on the less function
// Will return zeroValue of T and false if heap is empty
// Time complexity is O(1)
func (bh *BHeap[T]) Top() (T, bool)

// Removes the topmost node from the heap and returns the value along with true
// Will return the zeroValue of T along with false if the heap is empty
func (bh *BHeap[T]) Pop() (T, bool)

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

[gabyhelp]

Related Issues

• proposal: container: Generic Array Heap Implementation #73345
• proposal: container/heap: add Heap, a heap backed by a slice #47632
• proposal: Go 2: #63406 (closed)
• proposal: container/heap generic example #61993 (closed)

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

[seankhliao]

let's settle on a standard set of apis first in #47632 before thinking about other implementations