adt::Heap

Абстрактный тип данных “Куча”

Блокноты MuPAD® будут демонтированы в будущем релизе. Используйте live скрипты MATLAB® вместо этого.

Live скрипты MATLAB поддерживают большую часть функциональности MuPAD, хотя существуют некоторые различия. Для получения дополнительной информации смотрите, Преобразуют Notebook MuPAD в Live скрипты MATLAB.

Синтаксис

adt::Heap()

Описание

adt::Heap реализует абстрактный тип данных “Куча”.

“Куча” или “приоритетная очередь” являются типом данных, который хранит набор элементов. Элементы могут быть сравнены, и минимальный элемент может быть считан и удален из кучи.

В adt::Heap, каждый элемент сопоставлен с ключом сравнения, обычно вещественное число. Ключи должны быть сопоставимы друг с другом использующим <.

Получить доступ к самому большому элементу в adt::Heap, можно просто инвертировать ключи сравнения.

adt::Heap возвращает функциональную среду. Этот объект имеет пазы "insert", "nops", "min_pair", "min_element", и "delete_min" которые позволяют операции на куче. Смотрите примеры.

adt::Heap не предоставляет доступ к другим элементам, чем минимальный.

Примеры

Пример 1

adt::Heap() создает пустую кучу:

h := adt::Heap()

Паз "nops" из h показывает число элементов в куче:

h::nops()

h::insert метод должен вставить новые элементы. Это ожидает два аргумента: ключ сравнения и данные. На данный момент мы просто вставляем некоторые числа, таким образом, мы повторяем номер в обоих аргументах:

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

При получении элементов с h::delete_min, мы видим, что они возвращены в увеличивающемся порядке:

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

Куча теперь пуста:

h::nops()

Вызов delete_min на пустой куче возвращает FAIL:

h::delete_min()

Алгоритмы

adt::Heap использует полное двоичное дерево, сохраненное в списке. Вставки действуют в ожидаемое постоянное время с худшим временем случая, логарифмическим в числе элементов в куче. Для "delete_min", и средним значением и время выполнения худшего случая является O (logn) с n размер кучи.

Смотрите также

Функции MuPAD

Для просмотра документации необходимо авторизоваться на сайте