Matematycznie: minimum(S)Zwrócenie elementu o najmniejszym kluczu.extract_min(S)Zwrócenie elementu o najmniejszym kluczu z jednoczesnym usunięciem go ze zbioru.decrease_key(S, x, k)Zmienia wartość klucza elementu x na nową wartość k przy założeniu, że jest ona nie większa niż aktualna wartość klucza. Kolejki priorytetowe tego typu są używane m.in. w symulatorach zdarzeń.
Przy założeniu, że dane są b-bitowymi liczbami całkowitymi, a pamięć komputera składa się z adresowalnych słów b-bitowych, można zaimplementować operację minimum działającą w czasie stałym, a operacje insert oraz extract-min w działające w czasie . Przy założeniu, że pamięć jest nieograniczona (lub przy założeniu pamięci liniowej przy użyciu randomizowanego haszowania) można uzyskać oszacowanie .
Przypisy
Kategoria:Struktury danych