【数据结构】什么是堆

什么是堆

简单讲解，仅供学习

堆（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 = il = 2 * i + 1r = 2 * i + 2if l < n and arr[l] > arr[largest]:largest = lif r < n and arr[r] > arr[largest]:largest = rif 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 heapqclass 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（优先级更高的元素）

A 算法*：

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

K-最小堆：

描述：在处理大量数据时，使用堆来维护当前最小的 K 个元素。
应用：用于实时数据流处理和数据筛选。