data-structures - 优先队列的时间？

Question

• 一个优先级列表构建一个包含 n 个节点的列表需要多长时间？它是如何在上述时间内做到这一点的？

• delete-min函数（检索最小元素并将其从列表中删除）需要多长时间？它是如何在上述时间内做到这一点的？

Answer 1

取决于您如何构建优先队列。如果您使用的是堆结构，则需要 nlogn 来构建优先级队列。我记得建立最小堆的方法也可以在 O(N) 中完成。查看 CLRS 了解更多信息。

查看堆结构以了解它是如何构建堆结构的。本质上，您的比较器将是节点的优先级。

delete-min 需要 O(logn)。再看堆数据结构。

http://en.wikipedia.org/wiki/Heap_%28data_structure%29

您还可以将链表用于优先级队列。对于链表，delete min 也是常量。但是，根据您的输入，构建优先级队列可能会上升到 O(N^2)。