堆数据结构

什么是堆？

堆是一种完全二叉树，而二叉树是每个节点最多有两个子节点的树。在了解堆数据结构之前，我们应该先了解完全二叉树。

什么是完全二叉树？

完全二叉树是一种二叉树，其中除了最后一层（即叶节点）之外，所有层都完全填满，并且所有节点都靠左对齐。

让我们通过一个例子来理解。

在上图中，我们可以看到除了叶节点之外，所有内部节点都已填满；因此，我们可以说上图是一棵完全二叉树。

上图显示，除了叶节点之外，所有内部节点都已填满，但叶节点被添加到右侧；因此，上图不是完全二叉树。

注意：堆树是一种特殊的平衡二叉树数据结构，其中根节点与其子节点进行比较并相应地排列。

我们如何排列树中的节点？

堆有两种类型

• 最小堆
• 最大堆

最小堆：父节点的值应小于或等于其任何一个子节点的值。

或

换句话说，最小堆可以定义为，对于每个节点 i，节点 i 的值大于或等于其父节点的值（根节点除外）。数学上，它可以定义为

A[父节点(i)] <= A[i]

让我们通过一个例子来理解最小堆。

在上图中，11 是根节点，根节点的值小于所有其他节点（左子节点或右子节点）的值。

最大堆：父节点的值应大于或等于其子节点的值。

或

换句话说，最大堆可以定义为，对于每个节点 i；节点 i 的值小于或等于其父节点的值（根节点除外）。数学上，它可以定义为

A[父节点(i)] >= A[i]

上图是一棵最大堆树，因为它满足最大堆的属性。现在，让我们看看最大堆的数组表示。

最大堆的时间复杂度

最大堆所需的总比较次数取决于树的高度。完全二叉树的高度总是 logn；因此，时间复杂度也是 O(logn)。

最大堆插入操作的算法。

让我们通过一个例子来理解最大堆.

在上图中，55 是父节点，它大于其两个子节点，而 11 是 9 和 8 的父节点，因此 11 也大于其两个子节点。因此，我们可以说上图是一棵最大堆树。

堆树中的插入

44, 33, 77, 11, 55, 88, 66

假设我们要创建一个最大堆树。要创建最大堆树，我们需要考虑以下两种情况

• 首先，我们需要以一种方式插入元素，以保持完全二叉树的属性。
• 其次，父节点的值应大于其任何一个子节点。

步骤 1：首先，我们将 44 元素插入树中，如下所示

步骤 2：下一个元素是 33。我们知道二叉树的插入总是从左侧开始，因此 44 将添加到 33 的左侧，如下所示

步骤 3：下一个元素是 77，它将添加到 44 的右侧，如下所示

如上图所示，它不满足最大堆的属性，即父节点 44 小于子节点 77。因此，我们将交换这两个值，如下所示

步骤 4：下一个元素是 11。节点 11 被添加到 33 的左侧，如下所示

步骤 5：下一个元素是 55。为了使其成为完全二叉树，我们将节点 55 添加到 33 的右侧，如下所示

如上图所示，它不满足最大堆的属性，因为 33<55，因此我们将交换这两个值，如下所示

步骤 6：下一个元素是 88。左子树已完成，因此我们将 88 添加到 44 的左侧，如下所示

如上图所示，它不满足最大堆的属性，因为 44<88，因此我们将交换这两个值，如下所示

再次，它违反了最大堆的属性，因为 88>77，因此我们将交换这两个值，如下所示

步骤 7：下一个元素是 66。为了构建一棵完全二叉树，我们将 66 元素添加到 77 的右侧，如下所示

在上图中，我们可以看到该树满足最大堆的属性；因此，它是一棵堆树。

堆树中的删除

在堆树的删除操作中，根节点总是被删除，并被最后一个元素替换。

让我们通过一个例子来理解删除操作。

步骤 1：在上图中，第一个 30 节点从树中删除，并被 15 元素替换，如下所示

现在我们将对树进行堆化。我们将检查 15 是否大于其任何一个子节点。15 小于 20，因此我们将交换这两个值，如下所示

再次，我们将 15 与其子节点进行比较。由于 15 大于 10，因此不会发生交换。

堆化树的算法