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

container/heap: Fix is not correct #12304

Closed
jonathantcummings opened this issue Aug 24, 2015 · 2 comments
Closed

container/heap: Fix is not correct #12304

jonathantcummings opened this issue Aug 24, 2015 · 2 comments

Comments

@jonathantcummings
Copy link

Documentation( http://golang.org/pkg/container/heap/#Fix ) states:
"Fix re-establishes the heap ordering after the element at index i has changed its value."

A simple test proves that this functionality is broken. Add 10 numbers 0->9 and the heap will look like this:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Change heap[9] to 0 making the heap look like this:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 0]
Call heap.Fix(9) and the heap looks like this:
[0, 0, 2, 3, 1, 5, 6, 7, 8, 4]

@cespare
Copy link
Contributor

cespare commented Aug 24, 2015

This is working as intended.

"Heap ordering" doesn't mean the slice (or other underlying heap.Interface implementation) is totally ordered. It means that it follows the heap invariant:

!h.Less(j, i) for 0 <= i < h.Len() and 2*i+1 <= j <= 2*i+2 and j < h.Len()

(see the Interface documentation).

@bradfitz
Copy link
Contributor

Please provide a play.golang.org code snippet demonstrating the problem.

@mikioh mikioh changed the title container/heap heap.Fix is not correct container/heap: Fix is not correct Aug 25, 2015
@golang golang locked and limited conversation to collaborators Aug 24, 2016
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Development

No branches or pull requests

4 participants