Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!thunder.mcrcim.mcgill.edu!snorkelwacker.mit.edu!usc!sdd.hp.com!spool.mu.edu!uunet!bellcore!salt!narain
From: narain@salt.bellcore.com (Sanjai Narain)
Newsgroups: comp.lang.prolog
Subject: Priority queues in Prolog
Message-ID: <255@salt.bellcore.com>
Date: 18 Feb 91 18:42:17 GMT
Organization: Bell Communications Research
Lines: 9

Another method of implementing priority queues is via leftist trees 
developed by C.A. Crane (see The art of computer programming, D. Knuth, 
vol. 3, pp. 150-152). They are especially suited to representation via
linked lists. Insertion and deletion are both O(logn), n the number of 
elements in the tree. I have implemented them (in Prolog) to maintain
event queues in a discrete-event simulation. The implementation is 
straightforward. 

Sanjai Narain