堆数据结构:什么是堆?最小堆和最大堆(示例)
什么是堆?
堆是一种特殊的树数据结构。堆由最顶层的节点组成,称为根(父节点)。它的第二个子节点是根的左子节点,而第三个节点是根的右子节点。连续的节点从左到右填充。父节点键与其后代的键进行比较,然后进行适当的排列。树很容易可视化,其中每个实体称为一个节点。节点具有唯一的键以供识别。
为什么需要堆数据结构?
以下是使用堆数据结构的主要原因:
- 堆数据结构允许以对数时间(O(log2n)。
- 树中的数据按照特定顺序排列。除了更新或查询最大值或最小值等内容外,程序员还可以找到父代与子代之间的关系。
- 您可以应用 文件对象模型 帮助您理解堆数据结构。
堆的类型
堆数据结构有各种用于处理堆数据结构中的插入和删除元素的算法,包括优先级队列、二叉堆、二项式堆和 堆排序.
- 优先级队列: 它是一种包含优先级对象的抽象数据结构。每个对象或项目都预先安排了优先级。因此,分配了更高优先级的对象或项目将比其他对象或项目更早获得服务。
- 二叉堆: 二叉堆适合删除、插入等简单的堆操作。
- 二项式堆: 二项式堆由一系列组成堆的二项式树集合组成。二项式堆树不是普通的树,因为它是严格定义的。二项式树中的元素总数始终为 2n 节点。
- 堆排序: 与大多数排序算法不同,堆排序使用 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系统蒸发散
为了找到一组数据中的最高值和最低值,您需要执行许多基本的堆操作,例如查找、删除和插入。由于元素会不断出现和消失,因此您必须:
- 找到最适合您的地方 – 在一堆物品中寻找一件物品。
- 插页 – 将新子项添加到堆中。
- 删除 – 从堆中删除一个节点。
创建堆
构造堆的过程称为创建堆。给定一个键列表,程序员创建一个空堆,然后使用基本堆操作一次插入其他键。
因此,让我们开始使用 Willaim 的方法构建最小堆,方法是将值 12,2,8,1、4、XNUMX、XNUMX 和 XNUMX 插入堆中。您可以从一个空堆开始,然后用其他元素依次填充它,从而构建具有 n 个元素的堆,耗时 O (nlogn)。
- Heapify:在插入算法中,它帮助将元素插入到堆中。检查堆数据结构的属性是否突出显示。
例如,最大堆化会检查父元素的值是否大于其子元素的值。然后可以使用交换等方法对元素进行排序。
- 合并:假设您需要将两个堆合并为一个,请使用合并堆将两个堆的值合并在一起。但是,原始堆仍然保留。
检查堆
检查堆是指检查堆数据结构中元素的数量并验证堆是否为空。
检查堆作为元素的排序或排队很重要。使用 Is-Empty() 检查是否有要处理的元素很重要。堆大小将有助于定位最大堆或最小堆。因此,您需要了解堆属性后面的元素。
- 尺码 – 返回堆的大小或长度。您可以知道有多少元素是按排序顺序排列的。
- 是空的 – 如果堆为 NULL,则返回 TRUE,否则返回 FALSE。
在这里,您将打印 优先级 循环然后检查 priorityQ 是否不为空。
//print head the head values While (!priorityQ.isEmpty()) { System.out.print(priorityQ.poll()+" ");
堆数据结构的用途
堆数据结构在现实生活中的许多编程应用中很有用,例如:
- 有助于垃圾邮件过滤。
- 实现图形算法。
- Opera系统负载平衡和数据压缩。
- 在统计数据中查找顺序。
- 实现优先级队列,您可以在对数时间内搜索列表中的项目。
- 堆数据结构也用于排序。
- 模拟排队的顾客。
- 中断处理 运行系统.
- 采用哈夫曼编码进行数据压缩。
堆优先级队列属性
- 在优先堆中,列表中的数据项相互比较以确定较小的元素。
- 一个元素被放置在队列中,然后被删除。
- 优先级队列中的每个元素都有一个与之相关的唯一编号,该编号被标识为优先级。
- 退出优先级队列时,最高优先级的元素将首先退出。
实现堆优先级队列的步骤 Java
JAVA 中的堆排序及其代码示例
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 the root and the largest element 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 带有代码示例
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]
接下来,您将了解 二分法
总结
- 堆是一种特殊的树形数据结构。让我们想象一棵有父母和孩子的家谱。
- 堆数据结构 Java 允许在对数时间内删除和插入 - O(log2n)。
- 堆积如山 Python 有各种用于处理堆数据结构中的插入和删除元素的算法,包括优先队列、二叉堆、二项式堆和堆排序。
- 在最小堆结构中,根节点的值等于或小于该节点上的子节点的值。
- 在最大堆的结构中,根节点(父节点)的值等于或大于其子节点的值。
- 检查堆是指检查堆数据结构中元素的数量并验证堆是否为空。