什么是堆
简单讲解,仅供学习
堆(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 个元素。
- 应用:用于实时数据流处理和数据筛选。