堆数据结构：什么是堆？
陈莎拉
什么是堆数据结构？
堆是一种特殊的树状数据结构。堆数据结构由一个称为根节点（父节点）的最顶层节点、根节点的左子节点和右子节点组成。后续节点从左到右依次填充。父节点与其子节点的键值进行比较，以确保数据排列正确。堆结构易于可视化，其中每个实体称为一个节点，每个节点都有一个唯一的键值用于标识。
简单来说，堆是一棵完全二叉树，它满足堆的特性：每个父节点与其子节点的顺序一致，这使得它非常适合优先级队列和堆排序。
为什么需要堆数据结构？
以下是使用堆的主要原因：
- 堆数据结构允许在对数时间内执行删除和插入操作——O(log )2n）。
- 树状图中的数据是按照特定顺序排列的。除了更新或查询最大值或最小值等值之外，程序员还可以查找父节点和子节点之间的关系。
- 您可以应用 文件对象模型 帮助您以可视化的方式理解堆数据结构。
- 堆支持高效的优先级队列操作，这对于 Dijkstra 最短路径算法和 Prim 最小生成树等图算法至关重要。
堆的类型
堆数据结构有多种处理元素插入和删除的算法，包括优先队列、二叉堆、二项堆等。 堆排序.
- 优先队列： 这是腹肌tract 是一种包含优先级对象的数据结构。每个对象或项都有一个预先设定的优先级。因此，优先级较高的对象或项会优先获得服务。
- 二叉堆： 二叉堆适用于简单的堆操作，例如删除和插入。它们是大多数标准库优先级队列的默认实现。
- 二项堆： 二项堆由一系列二项树的集合构成。二项堆树并非普通的树，它有着严格的定义。二项树中的元素总数始终等于 2^n。n 节点。
- 堆排序： 与其他大多数排序算法不同，堆排序使用 O(1) 的空间复杂度。它是一种基于比较的排序算法，首先将输入数据转换为最大堆，然后按升序进行排序。你可以将堆排序看作是升级版的二叉搜索树。
通常，堆数据结构采用两种策略。对于输入 12 – 8 – 4 – 2 和 1：
- 最小堆 顶部价值最低
- 最大堆 最高值位于顶部
最小堆
在最小堆结构中，根节点的值小于或等于其所有子节点的值。因此，最小堆的根节点存储的是最小值。最小堆也是一棵完全二叉树。
一旦树中存在最小堆，所有叶子节点都可能成为最大值的候选节点。但是，要获得精确的最大堆值，需要逐个检查每个叶子节点。
最小堆示例
在上图中，您可以注意到从根节点到最底层节点的清晰顺序。
假设你将元素存储在数组 Array_N[12, 2, 8, 1, 4] 中。从数组中可以看出，根元素违反了最小堆的优先级规则。为了维护最小堆的性质，你需要执行最小堆化操作来交换元素，直到满足最小堆的规则为止。
最大堆
在最大堆结构中，父节点（或根节点）的值等于或大于其所有子节点的值。该节点存储着最大值。它是一个完全二叉树，因此可以在 O(n) 时间内从一组值构建一个最大堆。
以下是一些在实施过程中常用的方法 Java 最大堆：
- 添加 （）： 将新元素放入堆中。如果使用数组，对象会被添加到数组末尾；而在二叉树中，对象会从上到下，再从左到右依次添加。
- 消除 （）： 此方法允许您从数组列表中移除第一个元素。由于新移除的元素不再是最大的元素，因此 Sift-Down 方法总是会将其推入新的位置。
- 筛选（）： 该方法将根对象与其子对象进行比较，然后将重新定位的节点推送到其正确的位置。
- 筛选（）： 如果使用数组方法向数组中添加新元素，则 Sift-Up 方法会帮助新添加的节点重新定位到正确的位置。首先，通过模拟树状数据结构，将新元素与其父元素进行比较。
应用公式 Parent_Index = Child_Index / 2。继续执行此操作，直到最大元素位于数组的开头。
基本堆 Opera系统蒸发散
要查找数据集中的最大值和最小值，您需要用到一些基本的堆操作，例如查找、插入和删除。由于元素会不断地被添加和删除，您应该了解如何：
- 找到最适合您的地方 – 在一堆物品中寻找一件物品。
- 插页 – 将新子项添加到堆中。
- 删除 – 从堆中删除一个节点。
创建堆
构建堆的过程称为创建堆。给定一个键列表，程序员创建一个空堆，然后使用基本的堆操作将其他键逐个插入到堆中。
所以，让我们开始使用威廉的方法构建一个最小堆，首先插入值 12、2、8、1 和 4。你可以从一个空堆开始，然后依次用其他元素填充它，从而构建一个具有 n 个元素的堆，时间复杂度为 O(n log n)。
- 堆化： 一种插入例程，用于在保持堆属性的同时将元素插入堆中。
例如，最大堆化操作会检查父元素的值是否大于其子元素的值。然后可以使用诸如交换之类的方法对元素进行排序。ping.
- 合并： 当需要将两个堆合并成一个堆时，请使用合并操作将两个堆中的值合并在一起。原始堆仍然会被保留。
检查堆
检查堆是指检查堆数据结构中的元素数量，并验证堆是否为空。
在对元素进行排序或排队时，检查堆的大小至关重要。使用 `Is-Empty()` 函数检查堆中是否有待处理的元素非常重要。堆的大小有助于定位最大堆或最小堆的根节点，因此您需要知道堆中有多少元素遵循该属性。
- 尺寸 – 返回堆的大小或长度。它告诉你按排序顺序存储了多少个元素。
- 为空 – 如果堆为空，则返回 TRUE，否则返回 FALSE。
在这里，您将打印 优先级 循环然后检查 priorityQ 是否不为空。
//print head the head values While (!priorityQ.isEmpty()) { System.out.print(priorityQ.poll()+" ");
堆数据结构的用途
堆数据结构在现实生活中的许多编程应用中都非常有用，例如：
- 有助于垃圾邮件过滤。
- 实现图算法，例如 Dijkstra 算法和 Prim 算法。
- Opera系统负载均衡和数据压缩。
- 查找顺序统计量，例如第 k 小的元素。
- 实现优先级队列，可以在对数时间内搜索列表中的项目。
- 堆数据结构也用于通过堆排序进行排序。
- 模拟顾客排队等候的情况。
- 中断处理 运行系统.
- 在霍夫曼编码中用于数据压缩。
- 为人工智能路径规划中的最佳优先搜索和 A* 启发式算法提供支持。
堆优先级队列属性
以下属性描述了基于堆构建的优先级队列的行为方式：
- 在优先级堆中，列表中的数据项相互比较，以确定较小或较大的元素。
- 元素被放入队列，然后按优先级顺序移除。
- 优先级队列中的每个元素都有一个唯一的编号，用于标识其优先级。
- 退出优先级队列时，优先级最高的元素首先退出。
实现堆优先级队列的步骤 Java
下一部分将进入具体讨论。 Java 实现将这些规则转化为可运行的代码。
堆排序 Java - Code 例如：
import java.util.Arrays; public class HeapSort { public static void main(String[] args) { int[] arr = {5, 9, 3, 1, 8, 6}; // Sort the array using heap sort heapSort(arr); // Print the sorted array System.out.println(Arrays.toString(arr)); } public static void heapSort(int[] arr) { // Convert the array into a heap for (int i = arr.length / 2 - 1; i >= 0; i--) { heapify(arr, arr.length, i); } // Extract the maximum element from the heap and place it at the end of the array for (int i = arr.length - 1; i >= 0; i--) { int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; heapify(arr, i, 0); } } public static void heapify(int[] arr, int n, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; // Find the largest element among the root, left child, and right child if (left < n && arr[left] > arr[largest]) { largest = left; } if (right < n && arr[right] > arr[largest]) { largest = right; } // If the largest element is not the root, swap and heapify the sub-tree if (largest != i) { int temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp; heapify(arr, n, largest); } } }
输出
Original Array: 5 9 3 1 8 6 Heap after insertion: 9 8 6 1 5 3 Heap after sorting: 1 3 5 6 8 9
堆排序 Python - Code 例如：
def heap_sort(arr): """ Sorts an array in ascending order using heap sort algorithm. Parameters: arr (list): The array to be sorted. Returns: list: The sorted array. """ n = len(arr) # Build a max heap from the array for i in range(n // 2 - 1, -1, -1): heapify(arr, n, i) # Extract elements from the heap one by one for i in range(n - 1, 0, -1): arr[0], arr[i] = arr[i], arr[0] # swap the root with the last element heapify(arr, i, 0) # heapify the reduced heap return arr def heapify(arr, n, i): """ Heapifies a subtree with the root at index i in the given array. Parameters: arr (list): The array containing the subtree to be heapified. n (int): The size of the subtree. i (int): The root index of the subtree. """ largest = i # initialize largest as the root left = 2 * i + 1 # left child index right = 2 * i + 2 # right child index # If left child is larger than root if left < n and arr[left] > arr[largest]: largest = left # If right child is larger than largest so far if right < n and arr[right] > arr[largest]: largest = right # If largest is not root if largest != i: arr[i], arr[largest] = ( arr[largest], arr[i], ) # swap the root with the largest element heapify(arr, n, largest) # recursively heapify the affected subtree arr = [4, 1, 3, 9, 7] sorted_arr = heap_sort(arr) print(sorted_arr)
输出
[1, 3, 4, 7, 9]
接下来，你将学习到…… 二分法.
