binary search trees and queues

[Petar Maymounkov]

Is it a correct observation that Go's package system has no
implementation of a binary search tree (like Red-Black or Splay) and
also no implementation of a Queue data structure.

I should clarify, a queue is a data structure that supports
INSERT(value), REMOVE-MIN, UPDATE(elm, new value).

Queues are used to implement BFS (breadth-first search trees).

Thanks,
--Petar

[⚖ Alexander "Surma" Surma]

> I should clarify, a queue is a data structure that supports
> INSERT(value), REMOVE-MIN, UPDATE(elm, new value).

Technically, a queue only needs push_back() and pop().
So, considering this, container/list can be used as a stack, a queue
and a deque.
But your requirements can be easily implemented with container/list as a base.

You are right however that there's no raw implementation of a binary tree.

--
Alexander "cussing-makes-my-arguments-even-more-valid" Surma

[Petar Maymounkov]

This is not the QUEUE you are thinking of .. please read my description.
The meaning of QUEUE in Data Structure world is different.

Cheers,
--Petar

2010/5/26 ⚖ Alexander "Surma" Surma <alexand...@googlemail.com>:

[Petar Maymounkov]

E.g. the pretty much best queue implementation is called a Fibonacci
Heap.
This might sound more familiar.

P

On May 26, 12:56 pm, Petar Maymounkov <pet...@gmail.com> wrote:
> This is not the QUEUE you are thinking of .. please read my description.
> The meaning of QUEUE in Data Structure world is different.
>
> Cheers,
> --Petar
>

> 2010/5/26 ⚖ Alexander "Surma" Surma <alexander.su...@googlemail.com>:

[roger peppe]

container/heap is almost there, but doesn't have UPDATE.

2010/5/26 Petar Maymounkov <pet...@gmail.com>:

[John Asmuth]

A "queue" and a "priority queue" are two different things.

And calling the fibonacci heap the "best" pqueue implementation is a
bit... misleading, if technically correct. It may be efficient, but
good luck writing the code!

On May 26, 12:56 pm, Petar Maymounkov <pet...@gmail.com> wrote:

> This is not the QUEUE you are thinking of .. please read my description.
> The meaning of QUEUE in Data Structure world is different.
>
> Cheers,
> --Petar
>

> 2010/5/26 ⚖ Alexander "Surma" Surma <alexander.su...@googlemail.com>: