From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-0.8 required=5.0 tests=BAYES_00,INVALID_DATE autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,43d7d94ae0906b7d X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 1994-11-15 10:33:18 PST Path: nntp.gmd.de!xlink.net!sol.ctr.columbia.edu!howland.reston.ans.net!pipex!uunet!news.uiowa.edu!news From: jones@pyrite.cs.uiowa.edu (Douglas W. Jones,201H MLH,3193350740,3193382879) Newsgroups: comp.lang.ada Subject: Re: binary heap Date: 15 Nov 1994 17:31:39 GMT Organization: University of Iowa, Iowa City, IA, USA Distribution: world Message-ID: <3aar9r$ks7@nexus.uiowa.edu> References: NNTP-Posting-Host: pyrite.cs.uiowa.edu Date: 1994-11-15T17:31:39+00:00 List-Id: In article , Tucker Taft wrote: >Here is some Ada 83 code for a binary heap used to implement a priority >queue (FIFO within priority); this code (or a slight variation of it) >has been used successfully for many years. But note that the binary heap, by the benchmarks I published some years ago, is about a factor of 2 slower than splay trees under the hold model (repeated steady-state insertion and deletion in a priority queue), and note that the heap requires that you know the maximum size of the priority queue in advance. Splay trees, being based on binary trees, are limited only by available memory. You can get my code from the STARS library or from: ftp://ftp.cs.uiowa.edu/pub/jones/event/splayada.txt.Z This is a generic Ada package. Although it's written and documented in terms of discrete event simulation, it is easy to use as a general puprose priority queue (the generic parameter TIME_TYPE is the type to be used for the priority field; all that is required is that there be an ">" operator. The generic parameter AUX_TYPE is the data enqueued in the priority queue. Doug Jones jones@cs.uiowa.edu