% Copyright The Numerical Algorithms Group Limited 1992-94. All rights reserved.
% !! DO NOT MODIFY THIS FILE BY HAND !! Created by ht.awk.
\newcommand{\HeapXmpTitle}{Heap}
\newcommand{\HeapXmpNumber}{9.32}
%
% =====================================================================
\begin{page}{HeapXmpPage}{9.32 Heap}
% =====================================================================
\beginscroll
The domain \spadtype{Heap(S)} implements a priority queue of
objects of type \spad{S} such that
%-% \HDindex{priority queue}{HeapXmpPage}{9.32}{Heap}
the operation \spadfunX{extract} removes and returns
the maximum element.
%-% \HDindex{heap}{HeapXmpPage}{9.32}{Heap}
The implementation represents heaps as flexible arrays
(see \downlink{`FlexibleArray'}{FlexibleArrayXmpPage}\ignore{FlexibleArray}).
The representation and algorithms give complexity
of \texht{$O(\log(n))$}{O(log n)} for insertion and extractions,
and \texht{$O(n)$}{O(n)} for construction.

\xtc{
Create a heap of six elements.
}{
\spadpaste{h := heap [-4,9,11,2,7,-7]\bound{h}}
}
\xtc{
Use \spadfunX{insert} to add an element.
}{
\spadpaste{insert!(3,h)\bound{h1}\free{h}}
}
\xtc{
The operation \spadfunX{extract} removes and returns
the maximum element.
}{
\spadpaste{extract! h\bound{h2}\free{h1}}
}
\xtc{
The internal structure of \spad{h} has been
appropriately adjusted.
}{
\spadpaste{h\free{h2}}
}
\xtc{
Now \spadfunX{extract} elements repeatedly
until none are left, collecting the elements in a list.
}{
\spadpaste{[extract!(h) while not empty?(h)]\bound{h2}}
}
\xtc{
Another way to produce the same result is by defining
a \userfun{heapsort} function.
}{
\spadpaste{heapsort(x) == (empty? x => []; cons(extract!(x),heapsort x))\bound{f}}
}
\xtc{
Create another sample heap.
}{
\spadpaste{h1 := heap [17,-4,9,-11,2,7,-7]\bound{h1}}
}
\xtc{
Apply \spadfun{heapsort} to present elements in order.
}{
\spadpaste{heapsort h1\free{f}}
}
\endscroll
\autobuttons
\end{page}
%