【数据结构】什么是堆

简介: 【数据结构】什么是堆

什么是堆

简单讲解,仅供学习

堆(Heap) 是一种特殊的完全二叉树,它满足堆的性质:

1、 最大堆(Max-Heap):对于任何一个节点 i,其值都不小于其子节点的值。换句话说,根节点的值是堆中最大的值。

2、 最小堆(Min-Heap):对于任何一个节点 i,其值都不大于其子节点的值。换句话说,根节点的值是堆中最小的值。

堆通常用于实现优先队列、堆排序等算法。

堆的定义和操作

1、堆的定义:堆是一个完全二叉树,每个节点的值与其子节点的值具有特定的关系(最大堆或最小堆)。

2、常见操作:

  • 插入(Insert):将新元素插入堆中,并维护堆的性质。
  • 删除最大/最小元素(Extract-Max/Min):删除堆中的最大元素(在最大堆中)或最小元素(在最小堆中),并重新调整堆以维持其性质。
  • 堆化(Heapify):调整堆的结构,使其符合堆的性质。
  • 构建堆(Build-Heap):将一个无序数组转化为一个堆。


使用堆的经典算法

堆排序(Heap Sort):

  • 描述:利用堆的性质进行排序。首先将数据构建成一个堆,然后逐步提取堆顶元素,并调整堆的结构,最终得到排序后的数组。
  • 步骤:
  • 构建最大堆。
  • 交换根节点(最大值)与最后一个节点。
  • 对剩余的节点进行堆化。
  • 重复步骤2和3,直到堆为空。
def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2
    if l < n and arr[l] > arr[largest]:
        largest = l
    if r < n and arr[r] > arr[largest]:
        largest = r
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

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)

优先队列(Priority Queue):

  • 描述:优先队列是一个数据结构,其中每个元素都有一个优先级,元素按照优先级进行排序,通常使用堆来实现。
  • 操作:
  • 插入:将新元素插入队列,并维护堆的性质。
  • 提取最大/最小:根据优先级提取最大或最小元素。
  • 调整优先级:更新元素的优先级并重新调整堆。
import heapq

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

    def push(self, item, priority):
        heapq.heappush(self.heap, (priority, item))

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

pq = PriorityQueue()
pq.push("task1", 2)
pq.push("task2", 1)
print(pq.pop())  # 输出:task2(优先级更高的元素)

推荐的经典案例

Dijkstra 算法:

  • 描述:使用优先队列(最小堆)来找到从源点到其他所有点的最短路径。
  • 应用:图算法中的经典问题,适用于路径规划和网络路由等场景。

A 算法*:

  • 描述:扩展了 Dijkstra 算法,引入启发式函数,使用优先队列来优化路径搜索。
  • 应用:用于最短路径问题,尤其在游戏开发和机器人导航中广泛应用。

K-最小堆:

  • 描述:在处理大量数据时,使用堆来维护当前最小的 K 个元素。
  • 应用:用于实时数据流处理和数据筛选。
相关文章
|
18天前
|
存储 JavaScript 前端开发
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
54 1
|
2月前
|
存储 Java
【数据结构】优先级队列(堆)从实现到应用详解
本文介绍了优先级队列的概念及其底层数据结构——堆。优先级队列根据元素的优先级而非插入顺序进行出队操作。JDK1.8中的`PriorityQueue`使用堆实现,堆分为大根堆和小根堆。大根堆中每个节点的值都不小于其子节点的值,小根堆则相反。文章详细讲解了如何通过数组模拟实现堆,并提供了创建、插入、删除以及获取堆顶元素的具体步骤。此外,还介绍了堆排序及解决Top K问题的应用,并展示了Java中`PriorityQueue`的基本用法和注意事项。
41 5
【数据结构】优先级队列(堆)从实现到应用详解
|
26天前
|
存储 算法 调度
数据结构--二叉树的顺序实现(堆实现)
数据结构--二叉树的顺序实现(堆实现)
|
27天前
|
存储 算法 分布式数据库
【初阶数据结构】理解堆的特性与应用:深入探索完全二叉树的独特魅力
【初阶数据结构】理解堆的特性与应用:深入探索完全二叉树的独特魅力
|
19天前
|
存储 算法
探索数据结构:分支的世界之二叉树与堆
探索数据结构:分支的世界之二叉树与堆
|
21天前
|
存储 算法 Java
【用Java学习数据结构系列】用堆实现优先级队列
【用Java学习数据结构系列】用堆实现优先级队列
28 0
|
23天前
|
存储 算法
【数据结构】二叉树——顺序结构——堆及其实现
【数据结构】二叉树——顺序结构——堆及其实现
|
25天前
【数据结构】大根堆和小根堆
【数据结构】大根堆和小根堆
19 0
|
26天前
|
存储 算法 搜索推荐
数据结构--堆的深度解析
数据结构--堆的深度解析
|
3月前
|
存储 算法
【数据结构】堆
【数据结构】堆