Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

A issue In BinaryHeap #249

Open
aqhan opened this issue May 7, 2024 · 0 comments
Open

A issue In BinaryHeap #249

aqhan opened this issue May 7, 2024 · 0 comments

Comments

@aqhan
Copy link

aqhan commented May 7, 2024

In BinaryHeap,a function called Push

func (heap *Heap[T]) Push(values ...T) {
	if len(values) == 1 {
		heap.list.Add(values[0])
		heap.bubbleUp()
	} else {
		// Reference: https://en.wikipedia.org/wiki/Binary_heap#Building_a_heap
		for _, value := range values {
			heap.list.Add(value)
		}
		size := heap.list.Size()/2 + 1
		for i := size; i >= 0; i-- {
			heap.bubbleDownIndex(i)
		}
	}
}

In size_ := heap.list.Size()/2 + 1
Adjusting the code to size_ := heap.list.Size()/2 - 1 would be a more suitable approach.

We just need internal node to heapify. For Push(3, 2, 1), we just need index 0 to heapify, for Push (7, 6, 5, 4, 3, 2, 1), index 0, 1, 2 should be bubbleDown instead of index for 0 to 4.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant