Documentation

This is machine translation

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

Note: This page has been translated by MathWorks. Please click here
To view all translated materals including this page, select Japan from the country navigator on the bottom of this page.

adt::Heap

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.

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.

See Also

MuPAD Functions

Was this topic helpful?