algorithm - 如何从数组中获取 X 个最大值

Question

我有数组:[2, 4, 5, 1, 4, 20]

如何从这个数组中获取 X 个最大值？

像这样:

getHighest(2): 25, 5
getHighest(3): 25, 5, 4

Answer 1

基本思想是创建前 X 项的优先级队列(最大堆)。然后，对于数组中的每个剩余项，如果它小于堆中的第一项，则从堆中删除第一项并添加新项。像这样:

heap = new maxHeap();
for (i = 0; i < X; i++)
{
    heap.Add(a[i]);
}
for (; i < a.Length; ++i)
{
    if (a[i] < heap.peek())
    {
        heap.removeFirst();
        heap.Add(a[i]);
    }
}
// at this point, the smallest X items are on the heap.
// Remove them:
while (!heap.IsEmpty())
{
    print(heap.removeFirst());
}

请注意，我上面描述的是如何从数组中获取 X 最小 项。如果你想要 X 最大，创建一个最小堆并将比较从 < 更改为至 > .