数据结构与算法-关于堆的基本存储介绍

2024-08-09 11:01:58 浏览数 (1)

引言

堆是一种特殊的树形数据结构，常用于实现优先队列。堆通常以完全二叉树的形式存储在数组中，这样可以高效地访问父节点、子节点以及兄弟节点。本文将深入探讨堆的基本存储原理，包括最大堆和最小堆的概念，并通过具体的案例代码详细说明堆的实现和操作。

一、堆的基本概念

堆是一种特殊的二叉树，具有以下性质：

  1. 形状属性：堆是一棵完全二叉树。
  2. 堆序性质：对于最大堆，每个节点的值都大于或等于其子节点的值；对于最小堆，每个节点的值都小于或等于其子节点的值。
二、堆的存储结构

在计算机内存中，堆通常使用数组来实现。对于数组中的第 i 个元素（索引从0开始），其左孩子索引为 2*i 1，右孩子索引为 2*i 2，父节点索引为 (i-1)/2（向下取整）。

三、堆的操作

堆的主要操作包括：

  1. 插入元素：将新元素添加到数组的末尾，并调整堆以保持堆序性质。
  2. 删除根节点：删除数组的第一个元素（堆顶），并将最后一个元素移动到根位置，然后重新调整堆。
  3. 获取根节点：直接访问数组的第一个元素即可获得堆顶元素。
四、堆的实现

接下来，我们将通过一个示例来详细了解堆的实现步骤。

1. 示例数组

考虑一个整数数组 arr = [5, 2, 4, 6, 1, 3]，我们将构建一个最大堆。

2. 最大堆的构建

构建最大堆的过程包括：

  1. 初始化：将数组中的元素按顺序放入数组。
  2. 下沉调整：从最后一个非叶子节点开始，向下调整以保持堆序性质。
代码语言：javascript复制
def heapify(arr, n, i):
    largest = i
    left = 2 * i   1
    right = 2 * i   2

    # 如果左孩子大于根
    if left < n and arr[left] > arr[largest]:
        largest = left

    # 如果右孩子大于当前最大的
    if right < n and arr[right] > arr[largest]:
        largest = right

    # 如果最大的不是根
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # 交换
        heapify(arr, n, largest)

def build_max_heap(arr):
    n = len(arr)

    # 从最后一个非叶子节点开始
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

# 示例数组
arr = [5, 2, 4, 6, 1, 3]
build_max_heap(arr)
print("Max Heap:", arr)
3. 插入元素

插入元素的过程包括：

  1. 添加到末尾：将新元素添加到数组的末尾。
  2. 上浮调整：将新元素与其父节点比较，并根据需要向上移动以保持堆序性质。
代码语言：javascript复制
def insert(arr, value):
    arr.append(value)
    i = len(arr) - 1
    while i > 0 and arr[(i-1)//2] < arr[i]:
        arr[i], arr[(i-1)//2] = arr[(i-1)//2], arr[i]
        i = (i-1) // 2

insert(arr, 7)
print("After Insertion:", arr)
4. 删除根节点

删除根节点的过程包括：

  1. 移动最后一个元素：将数组的最后一个元素移动到根位置。
  2. 下沉调整：从根节点开始向下调整以保持堆序性质。
代码语言：javascript复制
def delete_root(arr):
    if len(arr) == 0:
        return

    # 移动最后一个元素到根位置
    arr[0] = arr[-1]
    del arr[-1]

    # 下沉调整
    heapify(arr, len(arr), 0)

delete_root(arr)
print("After Deletion:", arr)
五、堆的时间复杂度分析
  • 构建堆：O(n)
  • 插入元素：O(log n)
  • 删除根节点：O(log n)
  • 获取根节点：O(1)

❤️❤️❤️觉得有用的话点个赞

存储 二叉树 数据结构与算法 数组 索引

0 人点赞