# 9.32 HeapΒΆ

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 (see FlexibleArrayXmpPage ). The representation and algorithms give complexity of O(log(n)) for insertion and extractions, and O(n) for construction.

Create a heap of six elements.

h := heap [-4,9,11,2,7,-7]


 [11,7,9,-4,2,-7]

Type: Heap Integer

Use insert! to add an element.

insert!(3,h)


 [11,7,9,-4,2,-7,3]

Type: Heap Integer

The operation extract! removes and returns the maximum element.

extract! h


 11

Type: PositiveInteger

The internal structure of h has been appropriately adjusted.

h


 [9,7,3,-4,2,-7]

Type: Heap Integer

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))


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