[Freeciv-Dev] Re: Priority queue for Dijkstra

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

On Sat, 16 Mar 2002, Raimar Falke wrote:

> > The current implementation of priority queue in gotohand.c is actually
> > O(1) --- as far as I can tell --- due to the limited set of possible
> > priorities.  But it's a bit ugly.  Maybe there is a standard heap method 
> > ( heap is O(log(n)) ) somewhere in C or hidden in freeciv code?
> 
> None that I know of. I found these (GPLed):
>     223     864    5646 heap.c
>      77     356    2206 heap.h
> 
> Do you think that a "real" priority queue performance or does it will
> "only" increase readability?

Raimar, you been drinking???

It would definitely increase performance of your goto agent from 
O(n log(n)) to O(log(n)).

Compared with the current mapqueue methods it will be inferior I am 
afraid.  But mapqueue is hardly extendable and priority queue is.

Readability of the "user" code will not change.  It's the internal 
representation of mapqueue that is ugly, not the interface.

Right now I just want my air route-finding to be working.  Later I will 
try to convert to the best queue.

G.