数据结构中的堆

有一种非常灵活和特殊的数据结构，我们可以单独使用它来解决许多有趣的问题。此外，这种数据结构的定义具有最佳意义，因此它与贪婪算法有着天然的联系。它的本质是一棵完全的二叉树。它的身份即将出现。这是数据结构中的堆。

堆叠的数据结构可以看作是一个完全二叉树的数组对象。通过分析，我们可以使用数组来实现它。由于堆本质上是一棵完全二叉树，因此可以直接使用二叉树的相关概念，如高度等。在实现二叉树时，树结点通常被定义为：

public class Node {

public T data;

public Node left;

public Node right;

public Node parent;

public int state;

public Node(T d) {

this.data = d;

}

}

也就是说，一个结点通常有左右儿童结点指针和父亲结点指针。但在完全二叉树中，这三个指针可以省略，因为完全二叉树的结点编号是有规律的。给出一个结点，假设它被标记为i，那么它的左孩子结点的下标是2i + 1.右孩子结点的下标是2i + 2.它的父结点是(i−1)/2。这样，我们就可以省略这些指针，直接将堆中的结点存储在数组中。

堆又分为最大堆和最小堆。根节点最大的堆称为最大堆或大根堆，根节点最小的堆称为最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。堆的性质很简单。如果是最大的堆，每个结点的结点值大于两个孩子的结点值。如果是最小堆，每个结点的结点值都小于儿童结点值。堆是非线性数据结构，相当于一维数组，有两个直接后继。

对于一个堆，如果堆顶元素不满足结点大于儿童结点的条件，它的两棵子树已经是最合格的堆，我们可以很容易地将其维护成最合格的堆。将堆顶元素与两个儿童结点中最大的元素交换，然后将交换的子树递归地进行维护。这是一个堆的过程。

if (arr.length <= 1)

return;

int n = (arr.length - 2) / 2;

while (n >= 0) {

maxHeapify(arr, arr.length, n);

n--;

}

}

我们谈论的方法是自下而上地建造堆。该方法用于堆放排序，可以减少空间的使用，但不利于扩展。相比之下，还有一种自上而下的堆放方法，这里就不介绍了。

动态分配和释放程序中使用的对象在程序中堆放。在以下情况下调用堆操作：

1.事先不知道程序所需对象的数量和大小。

2.对象太大，不适合堆栈分配器。

堆运行期间分配给代码和堆栈以外的部分内存。

传统上，操作系统和操作时间库都附着在堆上。当过程开始时，操作系统被称为过程堆的默认堆。如果不使用其他堆，则使用过程堆分配块。语言操作时间库也可以在一个过程中创建单独的堆。（例如，C 库在运行过程中创建了自己的堆。)除了这些特殊堆，应用程序可能会加载许多动态链接库 (DLL) 还可以创建和使用单独的堆。Win32 提供一组丰富的 API用于创建和使用专用堆。关于堆函数的优秀教程请参考 MSDN 平台 SDK 节点。

应用程序或 DLL 在创建特殊堆时，这些堆停留在过程空间中，并在过程范围内可访问。给定堆分配的任何数据都应由同一堆释放。（从一堆分配到另一堆是没有意义的。）

在所有虚拟内存系统中，堆放在操作系统的虚拟内存管理器上。语言运行时，堆也停留在虚拟内存上。在某些情况下，这些堆叠在操作系统的上层，但在语言操作中，堆叠通过分配大块来执行自己的内存管理。使用虚拟内存函数绕过操作系统堆，可以更好地分配和使用堆块。由前端分配器和后端分配器组成的典型堆实现。前端分配器维护固定大小块的自由列表。堆收到分配调用后，试图从前端列表中找到自由块。如果此操作失败，堆将从后端(保留和提交虚拟内存)分配一个大块以满足要求。每个块分配的费用通常会实现，这花费了执行周期，也减少了可用存储区。

单个全局锁可以防止多线程同时使用堆。该锁主要用于保护堆数据结构免受多线程的任意访问。当堆操作过于频繁时，锁会对性能产生负面影响。

堆积在数据结构中有一个特殊的位置，不能在一段时间内完全说清楚。我想有更深入的了解数据结构中堆的相关知识可以在我们的网站上查看相关课程，格物致知方是学习的基础。