堆数据结构:什么是堆?最小堆和最大堆(示例)

什么是堆?

堆是一种特殊的树数据结构。堆由最顶层的节点组成,称为根(父节点)。它的第二个子节点是根的左子节点,而第三个节点是根的右子节点。连续的节点从左到右填充。父节点键与其后代的键进行比较,然后进行适当的排列。树很容易可视化,其中每个实体称为一个节点。节点具有唯一的键以供识别。

为什么需要堆数据结构?

以下是使用堆数据结构的主要原因:

  • 堆数据结构允许以对数时间(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 有各种用于处理堆数据结构中的插入和删除元素的算法,包括优先队列、二叉堆、二项式堆和堆排序。
  • 在最小堆结构中,根节点的值等于或小于该节点上的子节点的值。
  • 在最大堆的结构中,根节点(父节点)的值等于或大于其子节点的值。
  • 检查堆是指检查堆数据结构中元素的数量并验证堆是否为空。