Documentation Center

  • Trial Software
  • Product Updates

adt::Heap

Abstract data type "Heap"

Use only in the MuPAD Notebook Interface.

This functionality does not run in MATLAB.

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?