====================================================================
Heap examples
====================================================================

The domain Heap(S) implements a priority queue of objects of type S
such that the operation extract! removes and returns the maximum
element.  The implementation represents heaps as flexible arrays The
representation and algorithms give complexity of O(log(n)) for
insertion and extractions, and O(n) for construction.

Create a heap of five elements:

   a:Heap INT:= heap [1,2,3,4,5]
        [5,4,2,1,3]

Use bag to convert a Bag into a Heap:

   bag([1,2,3,4,5])$Heap(INT)
        [5,4,3,1,2]

The operation copy can be used to copy a Heap:

   c:=copy a
        [5,4,2,1,3]

Use empty? to check if the heap is empty:

   empty? a
        false

Use empty to create a new, empty heap:
 
   b:=empty()$(Heap INT)
        []

and we can see that the newly created heap is empty:

   empty? b
        true

The eq? function compares the reference of one heap to another:

   eq?(a,c)
        false

The extract! function removes largest element of the heap:

   extract! a
        5

Now extract! elements repeatedly until none are left, collecting
the elements in a list.

  [extract!(h) while not empty?(h)]
    [9,7,3,2,- 4,- 7]
                      Type: List Integer

Another way to produce the same result is by defining a heapsort function.

  heapsort(x) == (empty? x => []; cons(extract!(x),heapsort x))
                      Type: Void

Create another sample heap.

  h1 := heap [17,-4,9,-11,2,7,-7]
    [17,2,9,- 11,- 4,7,- 7]
                      Type: Heap Integer

Apply heapsort to present elements in order.

  heapsort h1
    [17,9,7,2,- 4,- 7,- 11]
                      Type: List Integer

Heaps can be compared with =

   (a=c)@Boolean
        false

and ~=

   (a~=c)
       true

The inspect function shows the largest element in the heap:

   inspect a
       4

The insert! function adds an element to the heap:

   insert!(9,a)
       [9,4,2,1,3]

The map function applies a function to every element of the heap
and returns a new heap:

   map(x+->x+10,a)
       [19,14,12,11,13]

The original heap is unchanged:

   a
       [9,4,2,1,3]

The map! function applies a function to every element of the heap
and returns the original heap with modifications:

   map!(x+->x+10,a)
       [19,14,12,11,13]

The original heap has been modified:

   a
       [19,14,12,11,13]

The max function returns the largest element in the heap:

   max a
       19

The merge function takes two heaps and creates a new heap with
all of the elements:

   merge(a,c)
       [19,14,12,11,13,5,4,2,1,3]

Notice that the original heap is unchanged:

   a
       [19,14,12,11,13]

The merge! function takes two heaps and modifies the first heap
argument to contain all of the elements:

   merge!(a,c)
       [19,14,12,11,13,5,4,2,1,3]

Notice that the first argument was modified:

   a
       [19,14,12,11,13,5,4,2,1,3]

but the second argument was not:

   c
       [5,4,2,1,3]

A new, empty heap can be created with sample:

   sample()$Heap(INT)
       []

The # function gives the size of the heap:

   #a
       10 

The any? function tests each element against a predicate function
and returns true if any pass:

   any?(x+->(x=14),a)
       true

The every? function tests each element against a predicate function
and returns true if they all pass:

   every?(x+->(x=11),a)
       false

The parts function returns a list of the elements in the heap:

   parts a
       [19,14,12,11,13,5,4,2,1,3]

The size? predicate compares the size of the heap to a value:

   size?(a,9)
       false

The more? predicate asks if the heap size is larger than a value:

   more?(a,9)
       true

The less? predicate asks if the heap size is smaller than a value:

   less?(a,9)
       false

The members function returns a list of the elements of the heap:

   members a
       [19,14,12,11,13,5,4,2,1,3]

The member? predicate asks if an element is in the heap:

   member?(14,a)
       true

The count function has two forms, one of which counts the number
of copies of an element in the heap:

   count(14,a)
       1

The second form of the count function accepts a predicate to test
against each member of the heap and counts the number of true results:

   count(x+->(x>13),a)
       2

See Also:
o )show Stack
o )show ArrayStack
o )show Queue
o )show Dequeue
o )show Heap
o )show BagAggregate

