algorithm - 二叉堆中的最小元素？

Question

为什么在二进制堆中找到最小的事件需要 O(log V) 时间？（其中 V 是元素的数量）

快速排序分治算法需要 O(V) 时间来找到最小的元素。由于在二进制堆中找到最小元素几乎与快速排序相同（在每一步都将问题的大小除以 2，并且问题的数量保持不变）为什么它们的时间不同？

为什么使用快速排序查找最小元素和查找二进制堆中的最小元素需要不同的时间？

Answer 1

任何最小堆（不一定是二进制）都会O(1)及时为您提供最小的元素。这是因为最小的元素是堆的根（满足堆属性）。

我认为这里的问题是你混淆了你的数据结构。在未排序的列表中，任何算法都至少需要O(N)时间，其中 N 是元素的数量。

如果您的数据已经存储在堆结构中，那么可以及时提取最小值O(1)。然而值得注意的是，首先从未排序的列表中构建堆需要O(N)时间。

如果你有一个排序列表，那么你可以使用二进制搜索来找到最小的O(log N)时间。但同样，排序至少需要O(N).

Answer 2

假设您试图在最大堆中找到最小的元素，如您所说，它将花费 O(V) 时间，而不是 O(log V) 时间。问题不是在每一步都分成两半。因为，一旦确定它小于根，最小元素可能在 2 个子树中的任何一个中。因此，您需要遍历两个子树才能找到 min 元素。

Answer 3

假设您正在谈论与快速排序非常相似的基于枢轴的选择算法，那么在两种情况下找到最小值是根本不同的。我的意思是，基于快速排序的选择算法会选择一个枢轴并对元素进行分区，然后您就知道您要查找的数字在剩余的哪些段中。二进制堆没有类似的属性。堆的特殊属性是每个节点都小于它的父节点（假设我们谈论的是最大堆）。就像其他答案之一所说的那样，这限制了 O(log(V)) 的可行候选者的数量，因为这是您可以在二进制堆中拥有多少叶子。但是，（据我所知）你必须要么维护一个叶子列表，或者您的堆必须表示为一个数组，以便您从中获得时间复杂性的好处。如果您的堆存储为一组链接节点，其中只有一个指向第一个元素的指针，那么在最坏的情况下，您必须搜索其所有子节点以找到最小值，因为这是您甚至可以看到的唯一方法树叶。我知道这个问题已经有很多答案，而且大部分都是正确的，但我希望这能澄清一些事情。

此外，为了清楚起见，实际的快速排序排序算法（如果是随机的）在摊销 O(nlogn) 时间内运行。在排序数组中找到最小元素是 O(1)。