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 (log n) с n размер кучи.