narain@salt.bellcore.com (Sanjai Narain) (02/19/91)
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