我研究过最小堆和最大堆，我有几个问题：
- 排序数组是最小堆吗？
- 最大堆的最小值是多少？
问问题
40933 次
8 回答
34
当使用基于数组的堆实现时，从最低到最高排序的数组是最小堆。父节点值小于或等于其子节点（2i + 1 和 2i + 2，使用从零开始的数组）的最小堆属性适用于所有具有子节点的节点。
最大堆的最小值在其中一个叶节点中，但您不知道是哪个。由于根据定义，最小节点不能有任何子节点，因此它必须是叶子。然而，堆属性并没有指定叶节点如何相互比较，只与它们的父节点进行比较。
于 2010-06-24T19:18:50.113 回答
7
排序数组是最小堆吗？
是的，如果您使用的是典型的数组存储堆约定。
最大堆的最小值在哪里？
在其中一片叶子上。这究竟是未定义的。
于 2010-06-24T19:19:30.667 回答
3
您可以将二进制堆实现为索引 i 与 2*i+1 和 2*i+2 比较的数组（i 从 0 开始）。在最小堆中 a[i] < a[2*i+1] 和 a[i] < a[2*i+2]
所以
1. 排序数组是最小堆。
2. 它没有具体的索引。我们只知道它只是一片叶子
于 2010-12-08T11:49:29.687 回答
0
最大堆的最小值在哪里？
Ans: 最大堆可以用索引从 1 到 n 的简单数组来表示。第一个元素是最大堆的根。堆属性：索引 i 处的节点在 2i 处有左子节点，在 2i+1 处有右子节点（如果 2i 和 2i+1 小于堆大小，即数组长度）。
从索引 i+1 到 n 找到最大堆的叶节点。这里 i=n/2; n 是数组长度。并且其中一个叶节点具有最小值。
所以我们可以从 a[i+1] 到 a[n] 的值中找到 max heap 的最小值。找到最小值的时间复杂度是（ni）的顺序。
于 2011-11-06T18:36:06.603 回答
0
- 排序数组是最小堆？
如果它是按升序排列的 - 是的，一般来说它是一个最小堆，更准确地说 - 具有以下规则的二进制堆的数组实现：
- 索引为i的节点的子节点可以在索引2i + 1和2i + 2处找到
- 索引为i的节点的父节点可以在索引floor((i - 1)/2)处找到
同时，它不能反向工作——基于数组的二进制堆不会存储排序列表。
- 最大堆的最小值在哪里？
它没有定义，当您将密钥存储在最小堆中时，这不是您想要快速回答的问题。如果您希望能够在 O(1) 时间内查看堆的最小值和最大值，则可以使用Java 中的MinMaxPriorityQueue等类。
于 2015-03-20T13:18:11.113 回答
0
永远真实的事实是：
每个升序排序的列表都是一个 minheap。
试试看，这条规则也不例外！
于 2022-01-15T15:38:22.153 回答
0
数组可以按升序或降序排序。“A sorted array is min-heap”这句话是部分正确的。该语句的正确版本是“按升序排序的数组可以视为最小堆”，其补充语句是“按降序排序的数组可以视为最大堆”。
“按升序排序的数组可以被视为最小堆”
但请记住，“并非所有最小堆都可以采用升序排列的数组形式”。
关于最大堆的最小值，我们只知道它存在于叶子中，我们可以在 O(n) 中搜索它
于 2018-02-22T14:51:55.043 回答
0
排序数组是最小堆吗？
排序数组是最小堆或最大堆，但反之亦然不是真正
的最小堆或最大堆不一定是排序数组。
最大堆的最小值是多少？
根据定义，最大堆（或优先级队列）在 O(1) 时间内从集合中提供最大值。如果有人需要从最大堆中检索最小值，那么首先使用堆本身来解决这个问题是不对的。这就像期望堆栈提供 FIFO 访问或期望队列提供 LIFO 访问。
但是 jfyi ，最小值将在堆形成的树的叶子之一处。它可以在任何子树上。所以你需要另一种算法，它需要超过 O(1) 的时间来定位它。
附带说明：
具有 n 个元素的堆可能有 [ 1 到 (n+1)/2] 个叶子。
如果堆形成的树的高度是 h 那么堆将有多达 2^(h-1) 个叶子
于 2018-01-12T01:25:09.577 回答