rga*_*aut 3 algorithm priority-queue data-structures
Priority Queue以从集合中检索max或min元素而闻名.优先级队列上的两个常见操作是Insert和DeleteMin/DeleteMax.我们是否有支持Delete(x)的优先级队列？Delete(x)的含义是从优先级队列中删除项目x.
天真的方法是找到项目x并删除它,但它需要线性时间.我正在寻找一些更好的算法.
某些类型的优先级队列确实支持此操作.通常,您可以通过使用delete(x)操作接受x作为数据结构内的指针来指示应删除哪个元素来执行此操作.例如,在二进制堆或Fibonacci堆中,每个元素都存储为林中的节点,insert(x)操作可能会将指针传回指向包含元素x的节点,然后delete(x)可以跟随提供的指针可快速定位要删除的元素.
在大多数以这种方式支持delete(x)的优先级队列(Fibonacci堆,二项式堆,配对堆等)中,delete(x)的复杂性与delete-min的复杂性相同,但这取决于特定的实施数据结构.
希望这可以帮助!