如果您有一个使用链表实现的fifo队列，那么弹出具有最高值的节点的最有效方法是什么？
合并排序将为O（n log n）。扫描列表将是O（n）。
有人能提出更有效的方法吗？
队列必须保留fifo排序，该排序以通常的入队和出队方式操作，但有一个额外的方法，如popMax，它弹出并返回具有最高值的节点。
不需要任何代码，只需要一些想法！谢谢
popMax是否足够频繁，以至于将其从O（N）更改为O（logN）可以证明额外的存储空间（每个节点：两个指针加一个索引）和额外的复杂性and将入队和出队从O（1）更改为0（logN）？？
在我解决这个问题的许多次中（出于不同的原因和不同的雇主），上述问题的答案一直是"是"。但对你来说可能是"不"。所以，首先做出决定。
对O（N）的任何改进都需要能够从主序列的中间移除。如果主序列是一个仅向前链接的列表，那么现在它需要两个方向的链接：一个额外的指针。
一堆指针会花费另一个额外的指针（每个节点，但不在节点中）。但是，出队列需要能够从堆的中间移除，它将节点中的索引作为指向其在堆中位置的后指针。
如果这一切都值得的话，你可以很容易地找到（在线免费）priorityQueue/heap模板版本的源代码，并且应该很清楚如何创建堆，对象是node*，给堆的less函数比较指向的节点内部的值。
接下来，您将更改堆源代码（这就是您不简单使用std:：priority_queue的原因），以便每次它在队列中定位一个"对象"（意思是node*）时，都会进行某种回调，通知对象其新索引。
您还需要公开堆代码的一些内部内容。在任何像样的堆代码版本中，都有一点是，代码处理堆中索引x处的一个洞（缺少元素），方法是检查堆的最后一个元素是否可以正确地移动到那里（如果是这样做的话），或者如果没有将洞的正确子元素移动到洞中，并重复该子元素所在的新洞。通常，该代码不会以x作为输入向外部调用方公开。但它很容易暴露出来。dequeue函数需要这样才能从堆中删除从列表中删除的相同元素。
对于较少的额外存储，但可能有更多的执行时间（尽管每个函数仍然为O（logN））。您可以有一堆节点，而不是一堆node*。这就是为什么在对这种堆进行编码时，应该对notify回调进行一般性编码（类似于less）。然后，你的双链接列表有索引而不是指针（所以增长是稳健的），notify函数会更新前任的前向索引和继任者的后向索引。为了避免大量的特殊情况，您需要有一个完整的双环（可能包括一个虚拟节点），而不仅仅是端到端。
我自己还没有处理过这些细节（因为我从未在后C++11中重做过这些），但我认为上面讨论的通知函数的一个更优雅的替代方案是将对象（将在堆中）包装在一个允许移动但不允许复制的包装器中。通知要执行的操作将在移动期间执行。这使得std:：priority_queue更加接近您的需求，但据我所知，它仍然没有暴露代码中用于在任意位置填充漏洞的关键内部点。