search

oleiade / lane

Generic PriorityQueues, Queues, Stacks, and Deque data structures for Go
https://pkg.go.dev/github.com/oleiade/lane#pkg-types
MIT License
878 stars 76 forks source link

Priority queue bug when multiple elements share a priority #7

Closed andrei-m closed 8 years ago

andrei-m commented 10 years ago

If a min priority queue contains three or more elements with the same priority, Head() and Pop() return an unexpected result. e.g.

package main

import (
    "fmt"
    "github.com/oleiade/lane"
)

func main() {
    queue := lane.NewPQueue(lane.MINPQ)
    queue.Push("a", 2)
    queue.Push("b", 2)
    queue.Push("c", 2) // Commenting this out leads to the correct result
    queue.Push("d", 1)
    // expect "d", get "a"
    fmt.Println(queue.Head())
}

"a", "b" and "c" are pushed onto the queue with the same priority (2). "d" is pushed on with a higher priority according to the min-priority queue, so I expect it to become the head. Instead, "a" is returned. The queue behaves correctly if one of the elements with priority 2 is removed.

go version go1.2.2 darwin/amd64

oleiade commented 10 years ago

Hi @andrei-m

Thanks for the bug report! And really sorry for the response delay, these last weeks have been quite intense here. I'm gonna dig into it. Do you already have clues on how to fix it? (I really really love Pull Requests ;) )

jbenet commented 9 years ago

was this fixed? considering using lane in https://github.com/jbenet/go-ipfs

oleiade commented 9 years ago

Not yet unfortunately :-)

I'll give it a shot tonight and keep you updated accordingly!

oleiade commented 9 years ago

Better later than never. I've spotted a huge bug in the binary heap implementation. It has been fixed by the commit caccc29 and I have improved testing + added concurrent insertion/pop tests.

Let me know if it fixes the problem for you guys.

Sorry for the huge delay!

oleiade commented 8 years ago

No replies. Considering it fixed. Closing.