# Documentation

### This is machine translation

Translated by
Mouseover text to see original. Click the button below to return to the English verison of the page.

# `adt`::`Heap`

Abstract data type “Heap”

MATLAB live scripts support most MuPAD functionality, though there are some differences. For more information, see Convert MuPAD Notebooks to MATLAB Live Scripts.

## Syntax

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

## Description

`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.

## Examples

### Example 1

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

## Algorithms

`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(logn), with n the size of the heap.