Re: binary heap

[stt@spock.camb.inmet.com (Tucker Taft)]

In article <CzA7FF.K7s@inmet.camb.inmet.com>,
Tucker Taft <stt@spock.camb.inmet.com> 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