Article View: comp.lang.prolog
Article #1815Priority queues in Prolog
From: Sanjai Narain
Date: Mon, 18 Feb 1991 18:42
Date: Mon, 18 Feb 1991 18:42
9 lines
875 bytes
875 bytes
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
Technical Details
Message-ID:
<255@salt.bellcore.com>Path:
arc1-ca.pugleaf.net!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!narainShow Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!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