双端优先队列

Question

7

我有一组数据，想找到最大和最小的项（多次），最好的方法是什么？

对于对应应用感兴趣的人，我正在开发一个详细级别系统，需要找到具有最大和最小屏幕空间误差的项目。显然，每次我细分/合并项目时，都必须将其插入队列，但每次相机移动整个数据集都会改变 - 因此最好使用排序列表，并推迟添加新项目，直到下一次排序（因为它经常发生）。

- Martin

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Firas Assaad · Accepted Answer

你可以使用文献Min-Max Heaps and Generalized Priority Queues中描述的最小-最大堆：

提供了双端优先队列的简单实现。所提出的结构称为最小-最大堆，可以在线性时间内构建；与传统堆相比，它允许在常数时间内执行FindMin和FindMax操作；Insert、DeleteMin和DeleteMax操作可以在对数时间内执行。