给定标记为1到N的列表L,以及从考虑中"移除"随机元素的过程,如何有效地跟踪min(L)？

Question

问题几乎在标题中,但我说我有一个清单L.

L = [1,2,3,4,5]

min(L)= 1.现在我除去4.分钟仍1.然后我除去2.分钟仍1.然后我除去1. min是现在3.然后我删除3.分钟现在是5,等等.

我想知道是否有一种很好的方法可以随时跟踪列表的最小值,而无需执行min(L)或扫描整个列表等.

实际从列表中删除项目会产生效率成本,因为它必须移动其他所有内容.每次重新排序列表也很昂贵.有没有解决的办法？

Answer 1

要删除随机元素,您需要知道尚未删除哪些元素.

要了解最小元素,您需要对项目进行排序或扫描.

作为数组实现的最小堆巧妙地解决了这两个问题.删除项目的成本是O(log N),找到min的成本是O(1).这些项目连续存储在一个数组中,因此随机选择一个很容易,O(1).

此维基百科页面上描述了最小堆

顺便说一句,如果数据很大,您可以将它们留在原位并在最小堆中存储指针或索引,并相应地调整比较运算符.