排序数组是最小堆吗？最大堆的最小值是多少？
我研究了最小堆和最大堆，我有几个问题：
- 排序数组是最小堆吗？
- 最大堆的最小值是多少？
I have studied min-heaps and max-heaps, and I have a couple of questions:
- Is a sorted array a min-heap?
- What is the minimum value of a max-heap?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（8）
当使用基于数组的堆实现时，从最低到最高排序的数组是最小堆。父节点值小于或等于其子节点（2i + 1 和 2i + 2，使用从零开始的数组）的最小堆属性适用于所有具有子节点的节点。
最大堆的最小值位于其中一个叶节点中，但您不知道是哪一个。由于根据定义，最小节点不能有任何子节点，因此它必须是叶子。然而，堆属性并不指定叶节点如何相互比较，而仅指定其父节点。
An array sorted from lowest to highest is a min-heap when using the array-based heap implementation. The min-heap property that the parent node value is less than or equal to it's child nodes (2i + 1 and 2i + 2, using zero-based arrays) holds for all nodes that have children.
The minimum value of a max heap is in one of the leaf nodes, but you don't know which. Since the minimum node cannot, by definition, have any child nodes, it must be a leaf. The heap property, however, does not specify how leaf nodes compare with each other, only with their parent.
是的，如果您使用典型的数组存储堆约定。
在其中一片叶子上。到底哪个是未定义的。
Yes, if you're using the typical array-stored heap convention.
At one of the leaves. Which exactly is undefined.
您可以将二叉堆实现为索引 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
You can implement binary heap as a array for index i compare with 2*i+1 and 2*i+2 (i starts from 0). in min heap a[i] < a[2*i+1] and a[i] < a[2*i+2]
so
1 . A sorted array is a min heap.
2 . It hasn't specific index. All we know that it is just a leaf
I suggest you read this http://en.wikipedia.org/wiki/Binary_heap
最大堆的最小值在哪里？
Ans：最大堆可以使用索引从 1 到 n 的简单数组来表示。第一个元素是最大堆的根。
堆属性：索引 i 处的节点的左子节点为 2i，右子节点为 2i+1（如果 2i 和 2i+1 小于堆大小，即数组长度）。
最大堆的叶节点从索引 i+1 到 n 找到。这里i=n/2； n 是数组长度。并且其中一个叶节点具有最小值。
所以我们可以从a[i+1]到a[n]的值中找到max heap的最小值。找到最小值的时间复杂度是 order-of(ni)。
where is the minimum value of a max heap?
Ans: Max heap can be represented using simple array with index start from 1 to n. 1st element is the root of the max heap.
Heap property: The node at index i has left child at 2i and right child at 2i+1 (if 2i and 2i+1 are less than heap size i.e. array length).
Leaf nodes of the max heap are found from index i+1 to n. Here i=n/2; n is array length. And one of the leaf nodes has the minimum value.
So we can find the minimum value of max heap from the values of a[i+1] to a[n]. Time complexity to find minimum value is order-of(n-i).
如果它按升序排列 - 是的，一般来说它是一个最小堆，更准确地说 - 一个二元堆的数组实现，具有以下规则：
同时，它不能反向工作——基于数组的二进制堆不会存储排序列表。
它没有定义，并且当您将密钥存储在最小堆中时，这不是您想要快速回答的问题。如果您希望能够在 O(1) 时间内查看堆的最小值和最大值，您可以使用类似 MinMaxPriorityQueue。
If it is ordered ascending - yes, generally speaking it is a min heap, more precisely - an array implementation of a binary heap with the following rules:
At the same time, it doesn't work in reverse - an array-based binary heap will not store a sorted list.
It is not defined, and it is not the question that you want to answer quickly when you store your keys in a min heap. If you want to be able to peek both min and max of the heap in O(1) time, you can use classes like MinMaxPriorityQueue in Java.
排序数组要么是最小堆，要么是最大堆，但反之亦然则不然
最小堆或最大堆不一定是排序数组。
根据定义，最大堆（或优先级队列）可在 O(1) 时间内从集合中提供最大值。如果有人需要从最大堆中检索最小值，那么首先使用堆本身来解决这个问题是不正确的。这就像期望堆栈提供 FIFO 访问或期望队列提供 LIFO 访问一样。
但是 jfyi ，最小值将位于由堆形成的树的叶子之一处。它可以在任何子树上。所以你需要另一种算法，它需要花费超过 O(1) 的时间来定位它。
附注：
包含 n 个元素的堆可能有 [ 1 到 (n+1)/2] 个叶子。
如果堆形成的树的高度为 h，则堆最多有 2^(h-1) 个叶子
sorted array is either min-heap or max-heap but vice versa is not true
min-heap or max-heap are not necessarily sorted arrays.
max-heap (or priority queue) by definition provides max value from a collection in O(1) time. if anyone is required to retrieve min value from a max-heap then using heap itself in the first place for this problem is not right. it's like expecting a stack provide FIFO access or expecting queue to provide LIFO access.
But jfyi , min value will be at one of the leaves of the tree formed by heap. it could be on any subtree. so you need another algorithm which will take more than O(1) time to locate it.
As a side note:
A heap with n elements may have [ 1 to (n+1)/2] leaves.
If height of the tree formed by heap is h then heap will have upto 2^(h-1) leaves
数组可以按升序或降序排序。
“排序数组是最小堆”这一说法部分正确。该语句的正确版本是“按升序排序的数组可以视为最小堆”，其补充语句是“按降序排序的数组可以视为最大堆”。
“按升序排序的数组可以视为最小堆”，
但请记住“并非所有最小堆都可以采用按升序排序的数组形式”。
关于最大堆的最小值，我们只知道它存在于叶子中，我们可以在 O(n) 中搜索它
Arrays either can be sorted in ascending order or in descending order.
The statement "A sorted array is min-heap" is partially correct. The correct version of this statement is "An array sorted in ascending order is can be treated as min- heap" and its complementry statement is "An array sorted in descending order can be treated as max heap".
"An array sorted in ascending order is can be treated as min- heap"
But remember that "Not all min-heaps can take the form of array sorted in ascending order".
And about minimum value of max heap we only know that this is present in the leafs and we can search that in O(n)
始终正确的事实是：
每个按升序排序的列表都是一个最小堆。
尝试一下，这个规则也不例外！
Always True Fact is :
Every sorted list in ascending order is a minheap.
Try and test it, there is no exception about this rule!