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}