二进制堆中最小的元素？

-2

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

Quicksort分而治之算法花费O（V）时间来查找最小的元素。由于在二进制堆中查找最小元素与Quicksort几乎相同（在每一步中都将问题的大小除以2，问题的数量保持不变），为什么他们有不同的时间？

为什么找到使用Quicksort的最小元素并找到二进制堆中最小的元素需要不同的时间量？

2012-06-21 fdh

修改您的假设。 Quicksort没有找到最小的元素（相反，它排序，这是一个更大的和完全不同的问题），并且不会在O（V）中运行（在最坏的情况下，我假设你没有得到更具体的结果）。二进制堆给你O（1）中最小的元素，假设你只是检索它并不删除它（这需要重新排序以维护堆属性，并且这是需要O（log V）时间的那个步骤）。 – delnan

@delnan 1）二进制堆如何取O（n）？它不需要首先找到元素吗？二进制堆没有排序 - 父母只是比孩子大。 2）不会排序一组数字允许找到O（1）时间中的最小元素？因为如果一个集合被排序，最小的数字就是最后一个数字 – fdh

（1）我假设一个最小堆，这是常见的，并且对于这个用例来说效率更高。唯一的区别是* *小*元素放在最上面（即换掉>换成<）。（2）是的，你可以很容易地得到最小值，但这不是Quicksort（相反，它是一个独特的算法，恰好利用任何排序算法），它仍然不是O（V）*最坏情况* 。即使你击中O（V）平均值/最佳情况，你也可以找到最小值。通过'minx = xs [0]在O（V）中更简单（并且方法更低）。 for x in xs：minx = min（minx，x）'。 – delnan

任何min-heap（不一定是二进制）会给你O(1)时间中的最小元素。这是因为最小的元素是堆的根（满足堆属性）。

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

如果您的数据已经存储在堆结构中，则可以在O(1)时间内提取最小值。但值得注意的是，从未排序的列表中首先构建堆将花费O(N)时间。

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

来源

2012-06-21 19:58:28 tskuzzy

如何从未排序的列表构建一个二进制堆取O（n）？用最少的O（n log n）时间来对一组数字进行排序并使用Mergesort等算法？ – fdh

你正在谈论两件不同的事情。构建二进制堆与排序不同。有关算法，请参阅http://en.wikipedia.org/wiki/Binary_heap#Building_a_heap。 – tskuzzy

如果列表已排序，则不应将最小值设为O（1），因为它只是第一个（或最后一个，取决于排序顺序）项目？ – delnan

假设您正在尝试查找最大堆中的最小元素，如您所说，它将花费O（V）时间，而不是O（log V）时间。这个问题在每一步都没有分成两半。因为一旦你建立它比根部小，最小的元素可以在任何2子树中。因此，您需要遍历两个子树以找到最小元素。

来源

2012-06-21 19:59:30

假设您正在讨论基于枢轴的选择算法，它与quicksort非常相似，在两种情况下找到最小值都有根本的不同。我的意思是，基于快速排序的选择算法选择一个数据透视表并对您的元素进行分区，然后您知道剩余的数据段中您正在查找的数字是哪一个。二进制堆没有类似的属性。堆的特殊性质是每个节点都小于它的父节点（假设我们正在讨论最大堆）。就像其中一个其他答案所述，这限制了O（log（V））的可行候选数量，因为这是二进制堆中有多少叶子。但是，（据我所知），您必须保留叶子列表，或者您的堆必须表示为数组，以便从中获得时间复杂性优势。如果你的堆是作为一组链接节点存储的，它只有一个指向第一个元素的指针，在最坏的情况下，你必须搜索它的所有子节点才能找到最小值，因为这是唯一的方法，你甚至可以看到树叶。我知道这个问题已经有很多答案了，其中大部分都是正确的，但我希望这可以澄清一些事情。另外，为了清楚起见，实际的快速排序算法（如果是随机的）以分期O（nlogn）时间运行。在排序数组中找到最少的元素是O（1）。

来源

2012-06-21 22:32:58

二进制堆中最小的元素？

回答

相关问题