Abstract data type "Heap"

This functionality does not run in MATLAB.

```
adt::Heap()
```

`adt::Heap`

implements the abstract data type
"Heap".

A "heap" or "priority queue" is a data type that stores a collection of elements. Elements can be compared and the minimal element can be read and deleted from the heap.

In `adt::Heap`

, each element is associated
with a comparison key, typically a real number. The keys must be comparable
with one another using `<`

.

To get access to the largest element in an `adt::Heap`

,
you can simply negate the comparison keys.

`adt::Heap`

returns a function
environment. This object has slots `"insert"`

, `"nops"`

, `"min_pair"`

, `"min_element"`

,
and `"delete_min"`

which allow operations on the
heap. See the examples.

`adt::Heap`

does not allow access to other
elements than the minimal one.

`adt::Heap()`

creates an empty heap:

h := adt::Heap()

The slot `"nops"`

of `h`

shows
the number of elements in the heap:

h::nops()

`h::insert`

is the method to insert new elements.
It expects two arguments: the comparison key and the data. For now,
we simply insert some numbers, so we repeat the number in both arguments:

h::insert(3,3): h::insert(1,1): h::insert(2,2):

h::nops()

When retrieving the elements with `h::delete_min`

,
we see that they are returned in increasing order:

h::delete_min(), h::delete_min(), h::delete_min()

The heap is now empty:

h::nops()

Calling `delete_min`

on an empty heap returns `FAIL`

:

h::delete_min()

`adt::Heap`

uses a complete binary tree stored
in a list. Insertions operate in expected
constant time, with a worst case time logarithmic in the number of
elements in the heap. For `"delete_min"`

, both the
average and the worst-case running time are *O*(*log* *n*),
with *n* the
size of the heap.

Was this topic helpful?