Heapify vs Heap-Sort vs Construct Heap

Question

我正在学习堆数据结构，并且对标题中提到的堆函数感到非常困惑。

根据我的理解，max heapify的算法看起来非常类似于使用自顶向下的方法构建堆。甚至堆排序类似于堆的自顶向下构造，只是在每次迭代时将第一个元素推送到数组的末尾。

另外，我想知道在这些函数中，我们处理的是实际的二叉树还是数组？或者我们只是用一个数组来表示一个二叉树，然后重新排列它的元素？

Answer 1

PriorityQueue是一种抽象数据类型，其中每个元素都有一个与之关联的优先级。许多数据结构都实现了PriorityQueue。堆就是其中之一。我们可以根据需要使用它们。Min-Heap将高优先级给予最小元素，而Max-Heap将高优先级给予最大元素。

还有，我想知道在这些函数中，我们是在处理实际的二叉树还是数组？或者我们只是用一个数组来表示一个二叉树，然后重新排列它的元素？

堆基于二叉树结构，可以使用数组轻松地实现。您也可以使用实际的二叉树来实现这一点。

Heapify是在将元素插入或移除到堆中时涉及的操作。当我们将一个元素插入到堆中时，我们将它插入到数组的末尾，并执行HeapifyUp，这会将插入的元素冒泡到正确的位置。当从顶部(开始)删除元素时，我们从数组中取出最后一个元素并将其插入开始处，然后向下冒泡(HeapifyDown)该元素，直到它到达正确的位置。

This是一篇很好读的文章。

Answer 2

堆的定义:堆是一个完全的二叉树，它满足父节点值大于子节点值(在最大堆的情况下)或小于子节点的值(在最小堆的情况下)的属性。Heap的这个属性必须跟在每个节点后面，并且它的子节点在树的每个级别上。

存储在内存中:二叉树以数组的形式作为数据结构存储在内存中，遵循对元素排序的级别遍历，使得对于作为父级的每个索引i，子级将是2_i+1和2_i+2

堆(构造堆)是一种方法(自上而下或自下而上)，它将元素排列在任何数组中，以便当检查任何索引i作为父级时，索引2_i+1和2_i+2处的子节点值将遵循最大堆或最小堆属性。它不会按升序或降序对数组进行排序。

堆排序:升序或降序排序数组。顾名思义，我们在这里使用Heap BT属性来重新排列数组元素。堆排序是堆BT的一个应用。

通过Heap-：对输入数组进行排序的步骤

1. 使用堆(构造堆)逻辑按照最大堆或最小堆的顺序排列数组元素。(在逻辑上它将遵循堆BT属性，但在存储方面它仍然是一个数组)
2. 将一个循环放在数组上，从根节点开始，将其与上一个叶节点进行比较，如果需要，交换并删除叶节点。在其他数组中插入已删除的元素。执行此操作，直到删除所有节点。现在，当我们删除Heap中的任何节点时，我们需要将Heapify残差数组作为对Heap BT的删除操作的一部分。在数组中插入时删除的元素遵循升序(MIN-HEAP)或降序(MAX-HEAP)。这类似于选择排序，后者在每次遍历中进行比较时，将最大/最小元素放到最终位置，并在下一遍的比较中排除。