跳到主要内容

堆结构

堆（Heap）是一种特殊的树形数据结构，通常用于实现优先队列。堆的一个重要特性是：堆中的每个节点的值都满足特定的堆性质。根据堆性质的不同，堆可以分为最大堆和最小堆。

  • 最大堆：每个节点的值都大于或等于其子节点的值。
  • 最小堆：每个节点的值都小于或等于其子节点的值。

堆通常用数组来实现，因为堆是一个完全二叉树，数组可以高效地表示这种结构。

堆的性质​

堆的核心性质是堆序性，即堆中的每个节点都满足堆的性质。以最大堆为例：

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

最小堆则相反，根节点的值是堆中的最小值，每个父节点的值都小于或等于其子节点的值。

堆的实现​

堆通常用数组来表示。对于一个索引为 i 的节点：

  • 其左子节点的索引为 2i + 1。
  • 其右子节点的索引为 2i + 2。
  • 其父节点的索引为 (i - 1) / 2。

代码示例：最大堆的实现​

以下是一个最大堆的简单实现，展示了如何插入元素和删除最大元素。

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)
        self._sift_up(len(self.heap) - 1)

    def _sift_up(self, i):
        while i > 0 and self.heap[self.parent(i)] < self.heap[i]:
            self.heap[self.parent(i)], self.heap[i] = self.heap[i], self.heap[self.parent(i)]
            i = self.parent(i)

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

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

示例输入与输出​

python
heap = MaxHeap()
heap.insert(10)
heap.insert(20)
heap.insert(15)
heap.insert(30)
print(heap.extract_max())  # 输出: 30
print(heap.extract_max())  # 输出: 20

堆的应用场景​

堆结构在实际中有广泛的应用，以下是一些常见的应用场景：

  1. 优先队列：堆是实现优先队列的理想数据结构，因为它可以在 O(log n) 时间内插入和删除元素。
  2. 堆排序：堆排序是一种高效的排序算法，时间复杂度为 O(n log n)。
  3. Dijkstra 算法：在图的单源最短路径算法中，堆用于高效地选择下一个最短路径节点。
  4. Top K 问题：堆可以用于快速找到数据流中的前 K 个最大或最小元素。

总结​

堆是一种非常重要的数据结构，特别适合需要频繁插入和删除最大或最小元素的场景。通过数组实现堆，可以高效地维护堆的性质。堆的应用非常广泛，从优先队列到排序算法，再到图算法，堆都扮演着关键角色。

附加资源与练习​

通过本文的学习，你应该对堆结构有了初步的了解。继续练习和探索，你将能够更深入地掌握这一重要的数据结构。