异常教程

堆的基本存储（建议收藏）

更新时间:

💡一则或许对你有用的小广告

欢迎加入小哈的星球 ，你将获得：专属的项目实战 / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论

  • 新项目:《从零手撸：仿小红书（微服务架构）》 正在持续爆肝中，基于 Spring Cloud Alibaba + Spring Boot 3.x + JDK 17...，点击查看项目介绍 ;
  • 《从零手撸：前后端分离博客项目（全栈开发）》 2 期已完结，演示链接： http://116.62.199.48/ ;

截止目前， 星球 内专栏累计输出 82w+ 字，讲解图 3441+ 张，还在持续爆肝中.. 后续还会上新更多项目，目标是将 Java 领域典型的项目都整一波，如秒杀系统, 在线商城, IM 即时通讯，权限管理，Spring Cloud Alibaba 微服务等等，已有 2900+ 小伙伴加入学习 ，欢迎点击围观

堆的基本概念与特点

堆（Heap）是一种特殊的完全二叉树数据结构，在计算机科学和编程领域中具有广泛应用。它以“父节点与子节点满足特定顺序关系”为核心特性，分为最大堆（Max-Heap）和最小堆（Min-Heap）。最大堆中，每个父节点的值都不小于其子节点；而最小堆则相反，父节点的值都不大于子节点。

堆的结构特性使其在实现优先队列、排序算法（如堆排序）以及实时数据处理等场景中表现出色。例如，操作系统调度任务时，通常需要根据优先级动态调整任务顺序，此时堆的高效插入和删除操作就能发挥关键作用。

堆的存储方式：数组 vs. 链表

堆的存储方式直接影响其实现效率和灵活性。常见的存储方式包括数组和链表，两者各有优劣。

数组存储：快速访问与空间利用率

堆最常用的存储方式是数组。通过数组的线性特性，可以高效定位节点的父节点和子节点。例如，对于索引为 i 的节点：

  • 父节点的索引为 i // 2（向下取整）；
  • 左子节点的索引为 2 * i；
  • 右子节点的索引为 2 * i + 1。

优点：

  • 随机访问：通过索引直接访问任意节点，时间复杂度为 O(1)；
  • 空间效率高：无需额外指针存储，节省内存；
  • 动态扩容：支持通过动态数组（如 Python 列表或 Java 的 ArrayList）灵活调整容量。

缺点：

  • 容量限制：固定大小的数组在元素过多时可能溢出，需手动扩容；
  • 插入/删除操作的局部性：当频繁调整堆结构时，可能引发数据迁移的额外开销。

数组实现堆的代码示例（Python）

class MaxHeap:  
    def __init__(self):  
        self.heap = []  # 使用列表模拟数组  

    def insert(self, value):  
        self.heap.append(value)  
        self._sift_up(len(self.heap) - 1)  

    def _sift_up(self, index):  
        parent = (index - 1) // 2  
        while index > 0 and self.heap[index] > self.heap[parent]:  
            self.heap[index], self.heap[parent] = self.heap[parent], self.heap[index]  
            index = parent  
            parent = (index - 1) // 2

在上述代码中，insert 方法通过 append() 将新值加入数组尾部，再通过 _sift_up() 方法“上浮”新值，确保父节点始终大于子节点。

链表存储：动态扩展与灵活性

链表通过节点对象的指针关系构建堆结构，每个节点包含值、父节点指针和子节点指针。例如，一个节点的结构可能如下：

class HeapNode:  
    def __init__(self, value):  
        self.value = value  
        self.parent = None  
        self.left = None  
        self.right = None

优点：

  • 动态扩展：无需预先分配内存，可按需扩展；
  • 局部操作高效：插入或删除节点时仅需调整相邻节点的指针，无需移动大量数据。

缺点：

  • 访问效率低：查找特定节点需遍历路径，时间复杂度为 O(h)，其中 h 是树的高度；
  • 内存开销大：每个节点需额外存储指针，空间利用率较低。

链表实现堆的挑战

链表实现堆的核心难点在于维护堆的顺序关系。例如，当插入新节点时，需从叶节点向上逐层比较并调整父子关系，这可能需要遍历整个路径。因此，链表在实现堆时通常不如数组高效，仅在特定场景（如内存受限或动态结构频繁变化时）使用。

堆存储的优化与常见问题

空间优化：完全二叉树的存储特性

堆通常以完全二叉树形式存在，即除了最后一层外，其他层节点均被填满，且最后一层节点从左到右连续排列。这一特性使得堆的数组存储无需额外标记空缺节点，直接通过索引计算即可定位子节点。

动态扩容策略

当使用固定大小的数组实现堆时，需考虑扩容策略。例如，当数组满时，可将其容量翻倍：

def resize(self):  
    new_capacity = len(self.heap) * 2  
    self.heap = self.heap + [None] * (new_capacity - len(self.heap))

这一策略确保了插入操作的时间复杂度为摊还 O(1)。

索引越界与边界条件处理

在实现堆操作时，需注意索引的合法性。例如，在 _sift_up() 方法中，当 index 为 0（根节点）时，循环终止，避免访问父节点的越界问题。

堆的应用场景与代码示例

场景一：优先队列

优先队列要求元素按优先级顺序出队。通过堆结构，可以实现 O(log n) 时间复杂度的插入和弹出操作。例如，使用最小堆实现优先队列：

class PriorityQueue:  
    def __init__(self):  
        self.heap = []  

    def push(self, priority, item):  
        # 插入元组 (priority, item)，按优先级排序  
        heapq.heappush(self.heap, (priority, item))  

    def pop(self):  
        return heapq.heappop(self.heap)[1]

上述代码借助 Python 的 heapq 模块简化堆操作，push 和 pop 方法均通过底层堆的结构调整实现。

场景二：堆排序

堆排序通过构建最大堆，逐步将根节点（最大值）与末尾元素交换，并重新调整堆结构。其时间复杂度为 O(n log n)，适用于大规模数据排序：

def heap_sort(arr):  
    n = len(arr)  
    # 构建最大堆  
    for i in range(n // 2 - 1, -1, -1):  
        heapify(arr, n, i)  
    # 逐个提取元素  
    for i in range(n-1, 0, -1):  
        arr[i], arr[0] = arr[0], arr[i]  # 交换  
        heapify(arr, i, 0)  

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)

此示例通过 heapify 方法维护堆结构，确保每次调整后仍符合最大堆的性质。

堆存储的优缺点对比与选择建议

特性数组存储链表存储
访问速度快（O(1)）慢（O(h)）
空间效率高（无指针开销）低（需存储指针）
动态扩展支持（需手动扩容）天然支持
适用场景高频访问、固定结构场景动态结构、内存敏感场景

选择建议

  • 优先选择数组存储：当堆的规模较大且需要快速访问时（如实现优先队列或排序算法）；
  • 考虑链表存储：在内存受限或堆结构频繁变化的场景中（如实时动态调整的树形数据）。

结论

堆的基本存储方式是理解其高效性与适用场景的关键。通过数组的线性特性，堆能够以极低的时间复杂度实现插入、删除和查找操作，而链表则在灵活性上提供了另一种选择。无论是编程竞赛中的算法优化，还是实际开发中的数据处理，掌握堆的存储原理与实现细节，都能显著提升问题解决效率。

在实际应用中，开发者需根据具体需求权衡存储方式的优劣。例如，优先队列的实现通常选择数组存储以保证性能；而某些嵌入式系统或小型内存环境中，链表可能成为更优解。通过结合理论与实践，堆这一经典数据结构将继续在计算机科学中发挥重要作用。

最新发布

查看更多文章