1 files changed, 69 insertions, 0 deletions
diff --git a/src/hyper/pages/HEAP.ht b/src/hyper/pages/HEAP.ht
new file mode 100644
index 00000000..974e5dca
--- /dev/null
+++ b/src/hyper/pages/HEAP.ht
@@ -0,0 +1,69 @@
+% 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}
+%