掌握堆：深入数据结构与算法

Source: Dev.to

引言

堆是计算机科学中的一种基础数据结构，常用于实现优先队列和优化算法。本文将深入探讨堆的结构、操作及其应用。

堆的类型

堆是一种满足 堆属性 的专用树形数据结构。主要有两种类型：

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

堆的操作

插入

向堆中插入元素时，先将元素放在最底层，然后通过与父节点比较并在必要时交换来“上浮”，直至恢复堆属性。

def insert(heap, value):
    heap.append(value)
    index = len(heap) - 1
    while index > 0:
        parent_index = (index - 1) // 2
        if heap[parent_index] > heap[index]:
            heap[parent_index], heap[index] = heap[index], heap[parent_index]
            index = parent_index
        else:
            break

删除

删除元素时，通常的操作是移除根节点。用堆中最后一个元素替换根节点，然后通过“下沉”（heapify）来保持堆属性。

def delete_root(heap):
    root = heap[0]
    heap[0] = heap[-1]
    heap.pop()
    index = 0
    while True:
        left_child = 2 * index + 1
        right_child = 2 * index + 2
        if left_child < len(heap) and heap[left_child] < heap[index]:
            heap[left_child], heap[index] = heap[index], heap[left_child]
            index = left_child
        elif right_child < len(heap) and heap[right_child] < heap[index]:
            heap[right_child], heap[index] = heap[index], heap[right_child]
            index = right_child
        else:
            break

应用

堆在各种算法和数据结构中被广泛使用。一个常见的例子是 Dijkstra 最短路径算法，其中最小堆能够高效地提取具有最小暂定距离的节点。

结论

堆是强大的数据结构，在算法优化中发挥关键作用。掌握堆的操作可以提升问题解决能力，并轻松应对复杂的计算挑战。