[Olsr-dev] Improving SPF with binary heaps

[Saulo Queiroz]

Yes with a little remark to functions of type first/last. We have two kinds
o PQs: MINimum and MAXimum. In min PQs, item priority means being
associated to low values (case of Dijkstra). In this case, get_first would
return the item with lowest number but get_last doesn't make sense. Similar
situation happens for max priority queues.
....

the lower the priority number associated
Em 12/07/2015 04:26, "Henning Rogge" <(spam-protected)> escreveu:

> On Sun, Jul 12, 2015 at 3:48 AM, Saulo Queiroz <(spam-protected)>
> wrote:
> >> Basics for both lists and AVL trees in OONF (which is the base of
> OLSRv2)
> >> is
> >> - init
> >> - insert
> >> - remove
> >> - get(key)
> >> - get_first
> >> - get_last
> >>
> >> and a good way to iterate over the elements of the tree/list (which
> >> would enable me to write iterator macros like the ones in
> >>
> >>
> http://olsr.org/git/?p=oonf.git;a=blob;f=src-api/common/list.h;h=a6146dcc9eb4d70ef1c2ae32b382df0460d948b0;hb=master#l315
> >> ).
> >>
> >> Can we have the same functions for a binary heap?
> >
> > It is possible but i think few procedures don't sound reasonable because
> > binary heaps
> > are Priority Queues (PQs) by nature being different from the typical data
> > structures.
> > In general, one employs priority queues when all items are expected to
> leave
> > the structure until the end of the execution of a procedure (what is very
> > usual in the so-called "greedy algorithms" like Dijkstra). In "normal"
> data
> > structures, there is no problem if an item stay in the structure
> "forever".
>
> Okay,
>
> so its more like
>
> - insert
> - remove first/last
> - get first/last
>
> Maybe even with get and remove combined into the same function, so
> that you can get the first/last element of the heap and remove it.
>
> Does this make more sense?
>
> Henning
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.olsr.org/pipermail/olsr-dev/attachments/20150712/2955200c/attachment.html>