双重优先级队列

Question

我有一组数据，我想查找最大和最小的项目（多次），那么执行此操作的最佳方法是什么？

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

Answer 1

您可以使用如文中所述的最小 - 最大堆Min-Max Heaps and Generalized Priority Queues：

的简单实现双倍结束的优先级队列为 。建议的结构， 称为最小 - 最大堆，可以在 内建线性时间;与传统堆中的 相比，它允许在 恒定时间内执行FindMin和FindMax两个 ; Insert，DeleteMin和 DeleteMax操作可以在对数时间执行 。