我正在尝试以高效的复杂性实现员工队列。
当我将员工插入队列时，我会提供其 ID 号和分数。 我想维护一个按员工分数升序排序的队列。
到目前为止，可以使用由二进制堆实现的优先级队列解决问题，但我需要能够从队列中删除员工并通过其 ID 号更新员工。 据我所知，二进制堆不支持删除或更新元素的有效方法。
更新- O(n( 用于搜索元素 + O(1( 用于更新它。
删除 - O(n( 用于搜索元素 + O(nlg(n(( 用于重建堆。
是否有更合适的数据结构来解决这个问题？
你可以用一些额外的内存相当容易地做到这一点。
最简单的方法：只需将重复的ID添加到树中。然后保留一个哈希集(如果 ID 已排序，则保留位图(以了解您是否已经返回了某个 ID(以跳过稍后出现的重复项(。
更难一点：保留从 ID 到堆中位置的哈希映射。每次触摸堆时，都需要更新哈希映射。由于您知道元素的位置，因此可以在 O(1( 中更新它的分数，然后推送或弹出节点以恢复堆(这应该是 O(logN((。
另一个简单的替代方法：如果分数只是降低(假设您有一个最大堆(，那么您不会为更新做任何事情。当你想弹出顶部时，你重新计算分数，如果它应该改变，你把节点向下推。如果它仍然在顶部，您可以删除它，如果没有，您可以返回重新计算顶部元素的分数。更新仍然是 O(logN(，但当您尝试采用顶部元素时会产生成本。
同样对于删除任意元素，复杂度应为 O(logN(。你用最后一个元素交换它，然后调用 push 位置。