### Re: Optimizing basic operations

Derek,

insert_record is faulty. If you insert data on increasing
key values into a max-heap the code appears to generate a

You say that the tree is not balanced: but a heap is
required to be a coplete tree - no gaps except the bottom
row which is filled from left to right.

Code attached: (untested)

(* This is for a max-heap *)

```const M = 256;                       (* say *)

type  rec = array[1..26] of integer; (* say *)

var   Heap : array[1..M,0..1] of integer;
N : integer := 0;
Data : array[1..M] of rec;

(* Two procedures siftUp and siftDown which move a node *)
(* into its correct position in the heap. *)

procedure siftUp;
var i,p,t : integer;
begin
i := N;
while i > 1 do
p := i div 2;
if Heap[i,0] > Heap[p,0] then  (* swap *)
begin
t := Heap[i];
Heap[i] := Heap[p];
Heap[p] := t;
i := c
end
else                 (* stop *)
exit while;
end
end; (* siftUp *)

procedure siftDown;
var i,c,t : integer;
begin
i := 1;
c := 2;
while c <= N do
begin
if c < N and Heap[c,0] < Heap[c+1,0] then c := c+1;
if Heap[c,0] > Heap[i,0] then
t := Heap[c];
Heap[c] := Heap[i];
Heap[i] := t;
i := c;
c := 2*c
else (* stop *)
exit while;
end;
end; (* siftDown *)

(* Three procedures to add, remove and replace nodes.
Addition is always done at the end - it is the only
action that can cause an overflow. Take always takes
the root and can cause an underflow. Replace is not
required - it was written with respect to James's
problem find the top 100 elements in a list. *)

begin
N := N+1;            (* add a node *)
Heap[N,0] := r[1];
Data[Heap[N,1]] := r;
siftUp;

function take : rec;
var r integer;
begin
r := Heap[1,1];
Heap[1] := Heap[N];  (* copies both node value and pointer *)
Heap[N,1] := r;      (* N now points to the record to be dropped *)
N := N-1;
siftDown;
take := Data[r]
end; (* take *)

procedure replace(r : rec);
begin
Heap[1,0] := r[1];
Data[Heap[1,1]] := r; (* overwrites with new record *)
siftDown;
end; (* replace *)
```