This is machine translation

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


Abstract data type "Heap"

MuPAD® notebooks are not recommended. Use MATLAB® live scripts instead.

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




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.


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


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:


Calling delete_min on an empty heap returns FAIL:



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.

See Also

MuPAD Functions

Was this topic helpful?