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 08:44:30 PST Newsgroups: comp.lang.ada Path: nntp.gmd.de!newsserver.jvnc.net!news.cac.psu.edu!news.pop.psu.edu!hudson.lm.com!godot.cc.duq.edu!newsfeed.pitt.edu!gatech!bloom-beacon.mit.edu!news.bu.edu!inmet!spock!stt From: stt@spock.camb.inmet.com (Tucker Taft) Subject: Re: binary heap Message-ID: Sender: news@inmet.camb.inmet.com Organization: Intermetrics, Inc. References: <39qese$kcm@columbia.acc.brad.ac.uk> Date: Tue, 15 Nov 1994 15:59:23 GMT Date: 1994-11-15T15:59:23+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. Unfortunately, the "slight" variation was the difference between correct and incorrect ;-(. In transcribing this, I left out a "+1". The fix is marked below. > ... >package body Priority_Queue is > -- Implement a priority queue; greater priority means more urgent. > -- Internal representation is a binary heap, > -- plus an array of FIFO queues. > > -- Copyright (C) 1994 Intermetrics, Inc. Cambridge, MA 02138 > -- May be freely copied so long as this copyright notice is retained > > type FIFO_Queue_Header is > record > First, Last : Queue_Entry := null; > end record; > FIFO_Queues : array(Priority) of FIFO_Queue_Header; > -- Array of singly-linked FIFO queues > > Num_Prio : constant := Max_Prio - Min_Prio + 1; > type Heap_Count is range 0 .. Num_Prio; > subtype Heap_Index is Heap_Count range 1 .. Num_Prio; The above two lines should be: type Heap_Count is range 0 .. Num_Prio+1; subtype Heap_Index is Heap_Count range 1 .. Heap_Count'Last; The extra value ensures that you may assume in "remove" that each element in the heap either has 2 children or 0 children. > Heap : array(Heap_Index) of Priority := (Heap_Index => Min_Prio); > -- Heap of priority values, Heap(Heap'First) is highest priority > -- with non-empty FIFO queue; > -- Heap preinitialized to Min_Prio to simplify removal. etc... Sorry about that... -Tucker Taft stt@inmet.com