STL的优先队列中为何没有删除某个任意元素的方法呢?

发布于 09-02 12:17 字数 281 浏览 6 评论 0

STL中的优先队列,只有删除队首元素的方法,并没有删除队中某个元素的方法。
我知道,队列的定义就是只允许操作队首队尾。
但是,优先队列不就是一个堆的实现吗?
常见的堆的实现(比如算法第四版)中同样也是只有删除最值元素的方法。没有删除任意元素的方法。
请问,实现删除任意元素的方法有什么弊端吗?

目前我有一个需求:我需要快速的得到一个数组的最值,但是需要动态的维护这个数组(可能会插入一个元素,或者删除某个元素),思来想去觉得堆再合适不过了。然而发现我能找到的堆实现都没有删除任意元素的方法,这让我有些困惑。

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(2

陈甜2022-09-09 12:17:21

堆只能保证堆顶的根节点元素是最值,根节点的左右子树之间是不能保证有序的。如果要实现删除任意元素的方法,首先要查找到该元素,而查找的时间复杂度是O(N)的,效率太低,因此没有实现。

你的需求用一个平衡树可以满足,比如C++ STL里面的set.

一城柳絮吹成雪2022-09-09 12:17:21

既然是优先队列那么就是有序的,而且用来实现它的堆是一个特殊的数据结构,抛去查找的消耗,你删除了某一个元素,堆本身的性质可能就破坏了,这个是得不偿失的。。
这个你可以用stl中的set,实现大部分采用的红黑树实现,查找、插入、删除都非常高效

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文