【如何构建最小和最大堆】数据结构在计算机编程中非常重要，可以快速有效地组织、管理和存储数据 。数据结构对于任何开发人员来说都是其工具包中绝对必要的技能 。
此篇文章重点关注堆 ， 这是一种特殊的基于树的数据结构，它实现了完整的二叉树 。
文章插图
什么是堆？堆是一种高级的基于树的数据结构，主要用于排序和实现优先级队列 。它们是完全二叉树，具有以下特征：
- 除了叶节点（没有子节点的节点称为叶节点）之外，每个级别都已填充 。
- 每个节点最多有 2 个子节点 。
- 所有节点都尽可能远离左侧，这意味着每个子节点都位于其父节点的左侧 。
文章插图
堆使用完全二叉树来避免数组中出现漏洞 。完全二叉树是每个节点最多有两个子节点的树，除了叶节点可以为空之外，所有级别的节点都是满的 。堆是根据堆属性构建的，它将父节点键与其子节点键进行比较 。
在本文的后面部分，我们将详细讨论基于最小堆属性构建的最小堆和基于最大堆属性构建的最大堆 。需要注意的是，堆并不总是排序的，它们遵循的关键条件是最大或最小元素放置在根节点（顶部）上 ， 具体取决于它是最大堆还是最小堆 。堆数据结构与堆内存不同 。
堆的优点和缺点优点：
- 垃圾收集在堆内存上运行以释放对象使用的内存 。
- 堆很灵活，因为可以按任何顺序分配或删除内存 。
- 变量可以全局访问 。
- 它有助于找到最小和最大数字 。
- 与堆栈相比，堆需要更多的执行时间 。
- 堆内存中的内存管理更加复杂 ， 因为它是全局使用的 。
- 堆通常需要更多时间来计算 。
优先级队列是基于堆结构设计的 。它需要氧O ( log ( n ) ) 有效地插入（insert()）和删除（delete()）优先级队列中每个元素的时间 。
堆实现的优先级队列用于流行的算法，例如：
- 普利姆（Prim’s）算法
- 迪杰斯特拉算法
- 堆排序算法
- heapify：重新排列堆中的元素以保持堆属性 。
- insert：将项目添加到堆中，同时保持其堆属性 。
- delete：删除堆中的项目 。
- extract：返回一个项目的值，然后将其从堆中删除 。
- isEmpty： boolean，如果boolean为空则返回true，如果有节点则返回false 。
- size：返回堆的大小 。
- getMax()：返回堆中的最大值
- 在堆的开头（根）创建一个新节点 。
- 为其指定一个值 。
- 将子节点的值与父节点的值进行比较 。
- 如果父节点的值小于任一子节点的值（向左或向右），则交换节点 。
- 重复此操作，直到最大元素位于根父节点（此时可以说堆属性成立） 。
将新元素插入堆时也可以遵循这些步骤 。这里的关键是，无论在最大堆上执行什么操作，都必须维护堆属性 。要移除/删除最大堆中的根节点：
