跳转到内容

最大堆与最小堆

来自代码酷

最大堆与最小堆[编辑 | 编辑源代码]

最大堆(Max Heap)最小堆(Min Heap)是两种特殊的二叉树结构,属于优先队列的常见实现方式。它们满足堆性质(Heap Property),即父节点与子节点之间存在特定的大小关系。最大堆中,父节点的值总是大于或等于其子节点的值;最小堆中,父节点的值总是小于或等于其子节点的值。堆结构常用于高效地获取、插入和删除极值元素(最大值或最小值)。

堆的性质[编辑 | 编辑源代码]

堆是一种完全二叉树(Complete Binary Tree),即除了最后一层外,其他层都被完全填满,且最后一层的节点尽可能靠左排列。堆的主要性质如下:

  • 最大堆性质:对于任意节点 i,其值 A[i]A[2i]A[i]A[2i+1](如果子节点存在)。
  • 最小堆性质:对于任意节点 i,其值 A[i]A[2i]A[i]A[2i+1](如果子节点存在)。

堆通常用数组实现,其中:

  • 根节点存储在索引 1(或 0,取决于实现)。
  • 对于节点 i,其左子节点为 2i,右子节点为 2i+1,父节点为 i/2

堆的操作[编辑 | 编辑源代码]

插入元素(Heapify Up)[编辑 | 编辑源代码]

新元素插入到堆的末尾,然后通过与其父节点比较并交换(如果需要),逐步向上调整,直到满足堆性质。

删除极值元素(Heapify Down)[编辑 | 编辑源代码]

删除堆顶元素(最大值或最小值),将最后一个元素移到堆顶,然后通过与其子节点比较并交换(如果需要),逐步向下调整,直到满足堆性质。

构建堆[编辑 | 编辑源代码]

从最后一个非叶子节点开始,依次对每个节点执行向下调整(Heapify Down),最终构建一个合法的堆。

代码示例[编辑 | 编辑源代码]

以下是用 Python 实现最大堆和最小堆的代码示例:

最大堆实现[编辑 | 编辑源代码]

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

    def parent(self, i):
        return (i - 1) // 2

    def left_child(self, i):
        return 2 * i + 1

    def right_child(self, i):
        return 2 * i + 2

    def insert(self, key):
        self.heap.append(key)
        i = len(self.heap) - 1
        while i > 0 and self.heap[i] > self.heap[self.parent(i)]:
            self.heap[i], self.heap[self.parent(i)] = self.heap[self.parent(i)], self.heap[i]
            i = self.parent(i)

    def extract_max(self):
        if not self.heap:
            return None
        max_val = self.heap[0]
        self.heap[0] = self.heap[-1]
        self.heap.pop()
        self.heapify_down(0)
        return max_val

    def heapify_down(self, i):
        left = self.left_child(i)
        right = self.right_child(i)
        largest = i
        if left < len(self.heap) and self.heap[left] > self.heap[largest]:
            largest = left
        if right < len(self.heap) and self.heap[right] > self.heap[largest]:
            largest = right
        if largest != i:
            self.heap[i], self.heap[largest] = self.heap[largest], self.heap[i]
            self.heapify_down(largest)

# 示例用法
max_heap = MaxHeap()
max_heap.insert(10)
max_heap.insert(5)
max_heap.insert(20)
max_heap.insert(1)
print("Max heap elements extracted in order:")
print(max_heap.extract_max())  # 输出 20
print(max_heap.extract_max())  # 输出 10
print(max_heap.extract_max())  # 输出 5
print(max_heap.extract_max())  # 输出 1

最小堆实现[编辑 | 编辑源代码]

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

    def parent(self, i):
        return (i - 1) // 2

    def left_child(self, i):
        return 2 * i + 1

    def right_child(self, i):
        return 2 * i + 2

    def insert(self, key):
        self.heap.append(key)
        i = len(self.heap) - 1
        while i > 0 and self.heap[i] < self.heap[self.parent(i)]:
            self.heap[i], self.heap[self.parent(i)] = self.heap[self.parent(i)], self.heap[i]
            i = self.parent(i)

    def extract_min(self):
        if not self.heap:
            return None
        min_val = self.heap[0]
        self.heap[0] = self.heap[-1]
        self.heap.pop()
        self.heapify_down(0)
        return min_val

    def heapify_down(self, i):
        left = self.left_child(i)
        right = self.right_child(i)
        smallest = i
        if left < len(self.heap) and self.heap[left] < self.heap[smallest]:
            smallest = left
        if right < len(self.heap) and self.heap[right] < self.heap[smallest]:
            smallest = right
        if smallest != i:
            self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
            self.heapify_down(smallest)

# 示例用法
min_heap = MinHeap()
min_heap.insert(10)
min_heap.insert(5)
min_heap.insert(20)
min_heap.insert(1)
print("Min heap elements extracted in order:")
print(min_heap.extract_min())  # 输出 1
print(min_heap.extract_min())  # 输出 5
print(min_heap.extract_min())  # 输出 10
print(min_heap.extract_min())  # 输出 20

堆的可视化[编辑 | 编辑源代码]

以下是一个最大堆的示例(使用 Mermaid 绘制):

graph TD 20 --> 10 20 --> 5 10 --> 1 10 --> 7

  • 根节点 20 是最大值。
  • 每个父节点的值都大于或等于其子节点的值。

实际应用场景[编辑 | 编辑源代码]

堆在以下场景中非常有用:

1. 优先队列:堆是优先队列的高效实现方式,例如任务调度系统(总是执行优先级最高的任务)。 2. 堆排序:利用最大堆或最小堆进行排序,时间复杂度为 O(nlogn)。 3. Dijkstra 算法:在图的最短路径算法中,最小堆用于高效获取当前距离最小的节点。 4. Top-K 问题:例如从海量数据中找出前 K 个最大或最小的元素。

时间复杂度分析[编辑 | 编辑源代码]

堆的主要操作时间复杂度如下:

  • 插入元素(Insert):O(logn)
  • 删除极值元素(Extract-Max/Min):O(logn)
  • 获取极值(Peek):O(1)
  • 构建堆(Heapify):O(n)

总结[编辑 | 编辑源代码]

最大堆和最小堆是高效管理动态数据极值的重要数据结构。它们的核心思想是通过维护堆性质,使得插入、删除和获取极值操作的时间复杂度保持在 O(logn)。理解堆的实现和应用场景,对于解决优先队列相关问题和优化算法性能非常有帮助。