Does Go has out of the box priority queue (the one that I can just import from some module and start using like python's priority queue)?
I know that priority queues are often implemented using heap data structure and go has a heap package, which also suggests how to use it to implement a queue (in Example (PriorityQueue) ), which I can easily grab and use.
My question is this a recommended way to do this, or there is an out of the box Priority Queue package that I failed to find?
分享 Quoting Wikipedia:
a priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a "priority" associated with it. [...] While priority queues are often implemented with heaps, they are conceptually distinct from heaps. A priority queue is an abstract concept like "a list" or "a map";
Go provides some basic data structures that are used in most applications but leave the implementation of more specialized data structures to the programmer. For example, the go map can be used to trivially implement a set.
The example you link to uses a slice []*Item to represent the more abstract type heap.Interface and also the (even more abstract) type PriorityQueue. Go is about composition and I would say that implementing PriorityQueue in terms of heap operations is good practice.
This gives you control as a programmer. If you want thread safety, use the composition of PriorityQueue and sync.Mutex to make it thread safe. If you want a different implementation than a heap, make PriorityQueue an interface and you can implement it however you want.
Of course there's a trade-off. In this case, the implementation was ~25 lines of code. If the implementation was hundreds of lines you'd probably want to find a package that has done this already.
分享
