好资源导航 » 文章资讯 » 间隔堆操作的复杂性

间隔堆操作的复杂性

2024-05-16 12:12:06 463

双端优先级队列(DEPQ)或间隔堆具有以下操作-

是空的()

该函数执行检查DEPQ是否为空，如果为空则返回true。

尺寸()

该函数执行返回DEPQ中存在的元素总数。

getMin()

该函数执行以返回具有最低优先级的元素。

getMax()

该函数执行以返回具有最大优先级的元素。

放(z)

该函数执行以将元素z插入DEPQ中。

removeMin()

该函数执行以删除优先级最小的元素并返回该元素。

removeMax()

此函数执行以删除具有最高优先级的元素并返回该元素。

的操作isEmpty()，size()，getMin()，和getMax()消耗O(1)每次;

put(z)，removeMin()和分别removeMax()消耗O（logn）;

初始化n个元素间隔堆需要O(n)时间。