Data Structures Algorithms 简明教程
Heap Data Structure
堆是平衡二叉树数据结构的一个特例，其中将根节点键与其子节点进行比较并相应排列。如果 α 有子节点 β ，则：
Heap is a special case of balanced binary tree data structure where the root-node key is compared with its children and arranged accordingly. If α has child node β then −
key(α) ≥ key(β)
由于父级的值大于子级的值，因此此属性生成 Max Heap 。基于此标准，堆可以分为两种类型：
As the value of parent is greater than that of child, this property generates Max Heap. Based on this criteria, a heap can be of two types −
For Input → 35 33 42 10 14 19 27 44 26 31Min-Heap - 其中根节点的值小于或等于其任一子节点。
Min-Heap − Where the value of the root node is less than or equal to either of its children.
Max-Heap - 其中根节点的值大于或等于其任一子节点。
Max-Heap − Where the value of the root node is greater than or equal to either of its children.
两棵树都是使用相同的输入和到达顺序构建的。
Both trees are constructed using the same input and order of arrival.
Max Heap Construction Algorithm
我们将使用相同的示例来说明如何创建最大堆。创建最小堆的过程类似，但我们追求最小值而不是最大值。
We shall use the same example to demonstrate how a Max Heap is created. The procedure to create Min Heap is similar but we go for min values instead of max values.
我们将通过一次插入一个元素推导出最大堆的算法。在任何时候，堆都必须保持其属性。在插入时，我们还假设我们将一个节点插入到已经堆化的树中。
We are going to derive an algorithm for max heap by inserting one element at a time. At any point of time, heap must maintain its property. While insertion, we also assume that we are inserting a node in an already heapified tree.
Step 1 − Create a new node at the end of heap.
Step 2 − Assign new value to the node.
Step 3 − Compare the value of this child node with its parent.
Step 4 − If value of parent is less than child, then swap them.
Step 5 − Repeat step 3 & 4 until Heap property holds.Note - 在最小堆构造算法中，我们希望父节点的值小于子节点的值。
Note − In Min Heap construction algorithm, we expect the value of the parent node to be less than that of the child node.
让我们通过动画图解来了解最大堆的构造。我们考虑前面使用过的相同输入样本。
Let’s understand Max Heap construction by an animated illustration. We consider the same input sample that we used earlier.
Max Heap Deletion Algorithm
让我们推导出一个从最大堆中删除的算法。最大（或最小）堆中的删除始终发生在根处以删除最大（或最小）值。
Let us derive an algorithm to delete from max heap. Deletion in Max (or Min) Heap always happens at the root to remove the Maximum (or minimum) value.
Step 1 − Remove root node.
Step 2 − Move the last element of last level to root.
Step 3 − Compare the value of this child node with its parent.
Step 4 − If value of parent is less than child, then swap them.
Step 5 − Repeat step 3 & 4 until Heap property holds.