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
не предоставляет доступ к другим элементам, чем минимальный.
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 размер кучи.