每日学习一个数据结构-堆

什么是堆？

数据结构中的堆（Heap）是一类特殊的完全二叉树结构，它常被用作实现优先队列。堆在物理结构上通常是顺序存储的，即可以使用数组来表示。以下是堆的详细说明：

1. 堆的定义

• 堆的性质：堆中的每个节点的值都满足堆的性质，即对于最大堆，父节点的值总是大于或等于其子节点的值；对于最小堆，父节点的值总是小于或等于其子节点的值。
• 完全二叉树：堆总是一棵完全二叉树，这意味着除了最后一层外，每一层都被完全填满，并且所有节点都尽可能地向左对齐。

2. 堆的表示

• 数组表示：堆最常用的表示方式是用数组。在这种表示中，根节点位于数组的第一个位置（通常下标为0或1，取决于具体实现），然后根据完全二叉树的性质，任何节点的左子节点和右子节点的下标可以通过父节点的下标计算得出（对于下标从1开始的数组，左子节点为2i，右子节点为2i+1；对于下标从0开始的数组，左子节点为2i+1，右子节点为2i+2）。

3. 堆的类型

• 最大堆：根节点是堆中的最大元素，每个父节点的值都大于或等于其子节点的值。
• 最小堆：根节点是堆中的最小元素，每个父节点的值都小于或等于其子节点的值。

4. 堆的操作

• 建堆：给定一个无序的数组，通过一系列的比较和交换操作，将其转换为一个堆结构。建堆的过程通常是从最后一个非叶子节点开始，向上调整每个节点，直到根节点。
• 插入：在堆的末尾添加一个新元素，并通过一系列的比较和交换操作，将这个新元素上浮到正确的位置，以保持堆的性质。
• 删除：删除堆顶元素（即根节点），并将堆的最后一个元素移动到堆顶，然后通过一系列的比较和交换操作，将这个新堆顶元素下沉到正确的位置，以保持堆的性质。

5. 堆的应用

• 堆排序：堆排序是一种基于堆的选择排序算法，它利用堆这种数据结构所设计的一种排序算法。堆排序算法可以分为两个主要的过程——建堆和排序。首先，将待排序的序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。然后，将其与末尾元素进行交换，此时末尾就是最大值。然后将剩余n-1个序列重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。
• 优先队列：堆可以高效地实现优先队列，其中最大堆常用于实现最大优先队列，最小堆常用于实现最小优先队列。优先队列常用于需要快速访问最大或最小元素的场景，如任务调度、图的最短路径算法等。

综上所述，堆是一种非常高效的数据结构，它利用完全二叉树的性质，通过数组来表示，并支持多种操作，如建堆、插入和删除等。堆在算法和数据处理中有着广泛的应用，特别是在排序和优先队列方面。

最大堆构建过程详细说明

最大堆的构建过程是一个将无序数组或集合转换为满足最大堆性质（即父节点的值大于或等于其子节点的值）的完全二叉树的过程。以下是最大堆构建过程的详细说明：

一、最大堆的定义与性质

• 定义：最大堆（Max Heap）是一种特殊的完全二叉树，其中每个父节点的值都大于或等于其子节点的值。
• 性质：
  1. 结构性质：最大堆是一颗完全二叉树，除了叶子节点外，每个节点都有两个子节点。
  2. 堆序性质：对于任意节点i，其值大于等于其左右子节点的值。

二、构建过程

最大堆的构建过程通常分为两个步骤：

1. 从无序数组开始：首先，我们有一个无序的数组或集合，这个数组或集合将被转换为最大堆。

2. 找到最后一个非叶子节点：由于最大堆是完全二叉树，我们可以从最后一个非叶子节点开始构建最大堆。在数组中，这个节点的索引可以通过n/2计算得到，其中n是数组的长度。注意，这里的索引通常是从0开始的，但在某些实现中（如C++的STL中的std::priority_queue），索引可能是从1开始的。

3. 下沉调整（Heapify）：从最后一个非叶子节点开始，向上遍历到根节点。对于每个遍历到的节点，执行以下操作：

   • 将该节点与其子节点（左子节点和右子节点）进行比较。
   • 如果该节点的值小于其任何一个子节点的值，则将该节点与其较大的子节点交换位置。
   • 交换后，继续对交换上来的节点执行相同的操作，直到该节点成为叶子节点或满足最大堆的性质。

这个过程称为“下沉调整”（Heapify），因为它通过不断将节点向下移动（即与其子节点交换位置）来确保最大堆的性质。

三、示例

假设我们有一个无序数组[3, 1, 4, 1, 5, 9, 2, 6]，我们想要将其构建为最大堆。

1. 找到最后一个非叶子节点：数组长度为8，最后一个非叶子节点的索引为8/2 - 1 = 3（注意，这里假设索引从0开始）。

2. 从索引3开始，向上遍历到根节点：

   • 对索引3的节点（值为4）进行下沉调整，与其子节点（索引6的节点，值为2）交换位置，得到[3, 1, 2, 1, 5, 9, 4, 6]。
   • 对索引2的节点（值为1）进行下沉调整，发现无需交换。
   • 对索引1的节点（值为3）进行下沉调整，与其子节点（索引3的节点，值为2）交换位置，得到[3, 2, 9, 1, 5, 1, 4, 6]。
   • 对根节点（索引0的节点，值为3）进行下沉调整，最终得到最大堆[9, 3, 6, 1, 5, 2, 4, 1]。

四、结论

最大堆的构建过程是一个从下到上、从左到右的遍历过程，通过下沉调整来确保每个节点都满足最大堆的性质。这个过程的时间复杂度为O(n)，其中n是数组的长度。构建完成后，最大堆的根节点就是数组中的最大值。最小堆的操作过程和最大堆类似，这里就不做过多描述。

堆与树什么区别

堆和树之间存在密切的关系，具体体现在以下几个方面：

一、定义与特性

• 堆：堆是一种特殊的完全二叉树结构，它满足堆属性，即堆中每个节点的值都大于等于（或小于等于）其子节点的值。根据堆属性的不同，堆可以分为最大堆和最小堆。堆在物理上通常使用数组来表示，这使得堆的操作（如插入、删除等）能够高效地执行。
• 树：树是一种非线性的数据结构，由n（n>0）个有限节点组成一个具有层次关系的集合。树中的每个节点都可能有零个或多个子节点，但每个节点只有一个父节点（除了根节点没有父节点）。树的结构灵活，可以表示多种层次关系。

二、关系说明

1. 堆是树的一种特殊形式：堆是一种特殊的完全二叉树，它除了满足完全二叉树的性质外，还满足堆属性。因此，堆可以看作是树的一个子集，具有树的所有基本特性，但又有其独特的性质和应用场景。
2. 堆的存储方式：堆在物理上通常使用数组来表示，这是因为它可以高效地利用数组的随机访问特性来模拟树的结构。在数组中，堆的根节点通常位于数组的起始位置（索引0或1），并且可以通过简单的算术运算找到任何节点的父节点和子节点。这种存储方式使得堆的操作（如插入、删除等）能够非常快速地执行。
3. 堆的操作与树的遍历：堆的操作（如插入、删除等）通常涉及到节点的上浮和下沉，这些操作与树的遍历（如先序遍历、中序遍历等）有一定的相似性。然而，堆的操作更注重于维护堆的属性，而不是遍历整个树。

三、应用场景

• 堆：由于堆具有快速访问最大（或最小）元素的能力，因此它常被用于实现优先队列、堆排序等算法。在操作系统中，堆也被用于内存管理等方面。
• 树：树的应用场景非常广泛，包括文件系统的组织、数据库索引的实现、XML文档的解析等。树的结构灵活，能够表示多种复杂的层次关系。

综上所述，堆和树之间存在密切的关系。堆是树的一种特殊形式，具有独特的性质和应用场景。通过理解堆和树的关系，我们可以更好地掌握这两种数据结构的特点和应用方法。