Python 堆（Heap）详解|极客笔记

Python 堆（Heap）详解

堆（Heap）是一种常见的数据结构，在计算机科学中被广泛应用。它通常用于实现优先队列等高效的数据操作。本文将详细介绍堆的概念、构建方法和Python语言中的实现。

概念概述

堆是一个具有以下性质的完全二叉树：
1. 堆中任意节点的值总是不大于（或不小于）其子节点的值。
2. 堆总是一棵完全二叉树。

根据第一条性质，我们可以将堆分为最大堆和最小堆两种类型：

最大堆：父节点的值总是大于或等于任意一个子节点的值。
最小堆：父节点的值总是小于或等于任意一个子节点的值。

堆的构建

1. 最大堆

我们可以使用数组来表示一个堆。数组中的每个元素对应堆中的一个节点，同时满足以下性质：对于下标为i的元素，其左子节点的下标为2i+1，右子节点的下标为2i+2，父节点的下标为(i-1)//2。使用这种表示方法，我们可以通过调整元素的位置来维护堆的性质。

下面是构建最大堆的过程：
1. 从最后一个非叶子节点开始，依次向前调整每个节点的位置，使得其值不大于子节点的值。
2. 不断向前调整，直到根节点的位置，此时整个树成为一个最大堆。

def max_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]
        max_heapify(arr, n, largest)

def build_max_heap(arr):
    n = len(arr)

    for i in range(n // 2 - 1, -1, -1):
        max_heapify(arr, n, i)

# 示例
arr = [4, 10, 3, 5, 1]
build_max_heap(arr)
print(arr)  # Output: [10, 5, 3, 4, 1]

2. 最小堆

构建最小堆与构建最大堆类似，只需要在比较节点和子节点的大小时将不等号方向反转即可。

def min_heapify(arr, n, i):
    smallest = i
    l = 2 * i + 1
    r = 2 * i + 2

    if l < n and arr[l] < arr[smallest]:
        smallest = l

    if r < n and arr[r] < arr[smallest]:
        smallest = r

    if smallest != i:
        arr[i], arr[smallest] = arr[smallest], arr[i]
        min_heapify(arr, n, smallest)

def build_min_heap(arr):
    n = len(arr)

    for i in range(n // 2 - 1, -1, -1):
        min_heapify(arr, n, i)

# 示例
arr = [4, 10, 3, 5, 1]
build_min_heap(arr)
print(arr)  # Output: [1, 4, 3, 5, 10]

Python中的堆实现

Python标准库中提供了heapq模块，可以方便地实现堆的操作。heapq模块提供了一些基本的堆操作，如堆的插入、弹出等。

1. 创建堆

我们可以使用heapq模块中的heapify函数来将一个普通的列表转换为堆。

import heapq

arr = [4, 10, 3, 5, 1]
heapq.heapify(arr)
print(arr)  # Output: [1, 4, 3, 5, 10]

2. 插入元素

使用heappush函数可以将元素插入到堆中，并保持堆的性质。

import heapq

arr = [1, 4, 3, 5, 10]
heapq.heappush(arr, 7)
print(arr)  # Output: [1, 4, 3, 5, 10, 7]

3. 弹出元素

使用heappop函数可以弹出堆顶元素，并重新调整堆使得其继续保持堆的性质。

import heapq

arr = [1, 4, 3, 5, 10]
top_element = heapq.heappop(arr)
print(top_element)  # Output: 1
print(arr)  # Output: [3, 4, 10, 5]

总结

堆是一种重要的数据结构，可以高效地实现优先队列等操作。通过构建最大堆或最小堆，我们可以快速获取最大值或最小值，并实现相应的操作。在Python中，使用heapq模块可以方便地实现堆的操作。

Python 堆（Heap）详解