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: