我学习了最小堆和最大堆，并有几个问题:
- 一个排序数组是否是最小堆?
- 最大堆的最小值是多少?
8个回答
36
使用基于数组的堆实现时，从最低到最高排序的数组是一个最小堆。对于所有具有子节点的节点，父节点的值小于或等于其子节点（使用基于零的数组，子节点为2i + 1和2i + 2）。
最大堆的最小值在叶节点中的一个位置，但你不知道它在哪里。由于定义上最小节点不能有任何子节点，因此它必须是一个叶节点。然而，堆属性并没有指定叶节点如何相互比较，只是与它们的父节点比较。
- tvanfosson
7
已排序的数组是否是最小堆？
如果您使用典型的基于数组的堆约定，则是的。
最大堆的最小值在哪里？
在其中一个叶子节点。具体是哪个未定义。
- Ben S
3
你可以将二叉堆实现为一个数组，其中索引i与2*i+1和2*i+2进行比较（i从0开始）。在最小堆中，a[i] < a[2*i+1]且a[i] < a[2*i+2]。
所以：
1. 排序数组是最小堆。
2. 它没有特定的索引。我们只知道它是一个叶子节点。
我建议您阅读这个链接：http://en.wikipedia.org/wiki/Binary_heap
所以：
1. 排序数组是最小堆。
2. 它没有特定的索引。我们只知道它是一个叶子节点。
我建议您阅读这个链接：http://en.wikipedia.org/wiki/Binary_heap
- user467871
0
一个排序好的数组是一个最小堆吗？
如果按升序排序-是的，一般来说它是一个最小堆，更准确地说-是一个具有以下规则的二叉堆的数组实现：
- 节点索引为i的子节点可以在索引2i+1和2i+2处找到 - 节点索引为i的父节点可以在索引floor((i-1)/2)处找到
同时，反过来不行-基于数组的二叉堆将不会存储一个排序好的列表。
最大堆中的最小值在哪里？
这没有定义，并且当您将键存储在最小堆中时，这不是您想要快速回答的问题。如果您想要能够在O(1)时间内查看堆的最小值和最大值，则可以使用Java中的类如MinMaxPriorityQueue。
如果按升序排序-是的，一般来说它是一个最小堆，更准确地说-是一个具有以下规则的二叉堆的数组实现：
- 节点索引为i的子节点可以在索引2i+1和2i+2处找到 - 节点索引为i的父节点可以在索引floor((i-1)/2)处找到
同时，反过来不行-基于数组的二叉堆将不会存储一个排序好的列表。
最大堆中的最小值在哪里？
这没有定义，并且当您将键存储在最小堆中时，这不是您想要快速回答的问题。如果您想要能够在O(1)时间内查看堆的最小值和最大值，则可以使用Java中的类如MinMaxPriorityQueue。
- Vladimir
0
永恒的真理是：
每个按升序排序的列表都是一个最小堆。
尝试并测试它，这个规则没有例外！
- everyt4u
0
一个排序好的数组是最小堆吗？
排好序的数组可以是最小堆或最大堆，但反之则不一定成立。
最小堆或最大堆不一定是排序好的数组。
最大堆的最小值是多少？
最大堆（或优先队列）根据定义可以在O(1)时间内从集合中提供最大值。如果需要从最大堆中检索最小值，则首先使用堆本身解决此问题是不正确的。这就像期望栈提供FIFO访问或期望队列提供LIFO访问一样。
顺便说一下：
具有n个元素的堆可能具有[1到(n+1)/2]个叶子节点。
如果由堆形成的树的高度为h，则堆将具有多达2^(h-1)个叶子节点。
但是，最小值将位于堆形成的树的其中一个叶子上。它可以在任何子树上。因此，您需要另一个算法来定位它，这需要超过O(1)的时间。
排好序的数组可以是最小堆或最大堆，但反之则不一定成立。
最小堆或最大堆不一定是排序好的数组。
最大堆的最小值是多少？
最大堆（或优先队列）根据定义可以在O(1)时间内从集合中提供最大值。如果需要从最大堆中检索最小值，则首先使用堆本身解决此问题是不正确的。这就像期望栈提供FIFO访问或期望队列提供LIFO访问一样。
顺便说一下：
具有n个元素的堆可能具有[1到(n+1)/2]个叶子节点。
如果由堆形成的树的高度为h，则堆将具有多达2^(h-1)个叶子节点。
但是，最小值将位于堆形成的树的其中一个叶子上。它可以在任何子树上。因此，您需要另一个算法来定位它，这需要超过O(1)的时间。
- Nitin
0
数组可以按升序或降序排序。
说“一个排序好的数组是最小堆”这句话只是部分正确的。正确的版本应该是“一个按升序排序的数组可以被视为最小堆”，它的补充语句是“一个按降序排序的数组可以被视为最大堆”。
但请记住，“并不是所有的最小堆都可以采用按升序排序的形式”。
至于最大堆的最小值，我们只知道它存在于叶子节点中，我们可以在O(n)的时间内搜索到它。
- brainLoop
0
最大堆的最小值在哪里？
答：最大堆可以使用从1到n开始的简单数组表示。第一个元素是最大堆的根节点。 堆属性：索引为i的节点具有左子节点2i和右子节点2i+1（如果2i和2i+1小于堆大小，即数组长度）。
最大堆的叶节点从索引i+1到n找到。这里i=n/2；n是数组长度。其中一个叶节点具有最小值。
因此，我们可以从a[i+1]到a[n]的值中找到最大堆的最小值。查找最小值的时间复杂度为O(n-i)。
- Raj
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接