二叉堆的设计与分析

---

堆有多种类型，但是在本章中，我们将讨论二叉堆。二叉堆是一种数据结构，看起来类似于完全二叉树。堆数据结构遵循下面讨论的排序属性。通常，堆由数组表示。在本章中，我们用H表示堆。

由于堆的元素存储在数组中，考虑起始索引为1 ，第 i^个元素的父节点位置可以在⌊ i/2 ⌋处找到。第 i^个节点的左子节点和右子节点位于位置2i和2i + 1。

根据排序属性，二叉堆可以进一步分类为最大堆或最小堆。

最大堆

在这个堆中，某个节点的键值大于或等于最高子节点的键值。

因此，H[Parent(i)] ≥ H[i]

最小堆

在平均堆中，节点的键值小于或等于最低子节点的键值。

因此，H[Parent(i)] ≤ H[i]

在这种情况下，下面显示了关于最大堆的基本操作。在堆中插入和删除元素需要重新排列元素。因此，需要调用Heapify函数。

数组表示

完全二叉树可以用数组表示，使用层序遍历来存储其元素。

让我们考虑一个由数组H表示的堆（如下所示）。

考虑起始索引为0，使用级别顺序遍历，元素将保存在数组中，如下所示。

指数	0	1	2	3	4	5	6	7	8	...
元素	70	30	50	12	20	35	25	4	8	...

在这种情况下，堆上的操作是相对于最大堆来表示的。

要查找索引i处元素的父元素的索引，请使用以下算法Parent (numbers[], i) 。

Algorithm: Parent (numbers[], i) 
if i == 1 
   return NULL 
else 
   [i / 2]

可以使用以下算法找到索引i处元素的左子元素的索引： Left-Child (numbers[], i)。

Algorithm: Left-Child (numbers[], i) 
If 2 * i ≤ heapsize 
   return [2 * i] 
else 
   return NULL 

可以使用以下算法找到索引i处元素的右子元素的索引： Right-Child(numbers[], i)。

Algorithm: Right-Child (numbers[], i) 
if 2 * i < heapsize 
   return [2 * i + 1] 
else 
   return NULL