二叉堆

发表于 | 分类于 | 阅读次数:

综述

本文主要介绍二叉堆，也简称堆，为一种常见的数据结构。本文将从二叉堆的概念、二叉堆的实现、堆排序以及优先队列等进行阐述。本文的完整代码可以在我的github找到。

堆的概念

堆是一个数组，它可以被看成一个近似的完全二叉树。其概念定义如下：

对于数组X = {$x_i$, i=0, 1, 2, 3, …, n}，当且仅当$x_i<=x_{2i+1}, x_i<=x_{2i+2}, i=0, 1, 2, 3, .., \lfloor{n}\rfloor$，数组X为小根堆，当且仅当$x_i>=x_{2i+1}, x_i>=x_{2i+2}, i=1, 2, 3, .., \lfloor{n}\rfloor$，数组X为大根堆。因为堆可以看作近似的完全二叉树，因此可以证明其根结点的下标为$\lfloor{n/2}\rfloor +1, \lfloor{n/2}\rfloor +2, …, n$。注意下标为从0开始，因此可能与他处的定义略有不同。

堆的实现

下面以大根堆为例，介绍堆的操作。首先是堆的调整，其python代码示例如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def max_heapify(heap, i, n=None):
    if n is None:
        n = len(heap)

    left = i * 2 + 1
    right = left + 1
    largest = i
    if left < n and heap[left] > heap[largest]:
        largest = left

    if right < n and heap[right] > heap[largest]:
        largest = right

    if largest != i:
        heap[largest], heap[i] = heap[i], heap[largest]
        max_heapify(heap, largest, n)

最大堆的调整采用的是自顶向下的方法，每次调整以i为根的树，并满足以i的左右子结点为根的树已经满足大根堆的性质，交换i和其左右子节点的最大值，并对交换后的子结点进行递归处理。因为二叉堆的高为logn, 因此其时间复杂度为O(logn)。

从数组中创建大根堆即采用上述子过程，将其叶节点视为大根堆，非叶结点从后往前依次调整，使得每次调整前都满足左右结点已经为大根堆的条件。其python代码示例如下：

1
2
3
4
def build_max_heap(heap):
    n = len(heap)
    for i in reversed(range(n // 2)):
        max_heapify(heap, i, n)

因为非叶结点的最大下标为$\lfloor{n/2}\rfloor$，因此从$\lfloor{n/2}\rfloor$到0依次调整数组，使其成为大根堆。此大根堆的时间复杂度为O(nlogn)

对于大根堆的push和pop操作，其python代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def max_heappop(heap):
    n = len(heap)
    if n == 0:
        return None
    elif n == 1:
        item = heap.pop()
    else:
        item = heap[0]
        heap[0] = heap.pop()
        max_heapify(heap, 0)

    return item

def max_heappush(heap, item):
    heap.append(item)
    i = len(heap) - 1
    parentpos = (i - 1) // 2
    while i > 0 and heap[parentpos] < heap[i]:
        heap[parentpos], heap[i] = heap[i], heap[parentpos]
        i = parentpos
        parentpos = (i - 1) // 2

对于max_heappop操作，将大根堆的最大值弹出堆，并用数组最后的元素替换第0个元素，此时依然满足max_heapify的条件，直接调用max_heapify即可调整堆。对于max_heappush操作，我们将新加入的元素放至数组的最后，然后自底向上调整依次进行调整。因此这两种操作的时间复杂度均为O(logn)。

堆可用于排序，堆排序首先是原址排序，即其空间复杂度为O(1)，且其时间复杂度为O(nlogn)。其python代码示例如下：

1
2
3
4
5
def max_heap_sort(heap, size):
    build_max_heap(heap)
    for i in reversed(range(1, size)):
        heap[0], heap[i] = heap[i], heap[0]
        max_heapify(heap, 0, i)

优先队列

堆可以用来实现优先队列，与大根堆与小根堆相对应的是最大优先队列和最小优先队列。与上述大根堆的实现类似，我们以类的形式封装小根堆，其python 代码示例如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Heap:
    def __init__(self, arr=None):
        self.arr = arr if arr else []
        if self.arr:
            self.buildheap()

    def heappush(self, item):
        self.arr.append(item)
        i = len(self.arr) - 1
        parentpos = (i - 1) // 2
        while i > 0 and self.arr[parentpos] > self.arr[i]:
            self.arr[parentpos], self.arr[i] = self.arr[i], self.arr[parentpos]
            i = parentpos
            parentpos = (i - 1) // 2

    def buildheap(self):
        n = len(self.arr)
        for i in reversed(range(n // 2)):
            self.heapify(i)

    def heapify(self, i):
        n = len(self.arr)
        left = 2 * i + 1
        right = left + 1
        smallest = i
        if left < n and self.arr[left] < self.arr[smallest]:
            smallest = left

        if right < n and self.arr[right] < self.arr[smallest]:
            smallest = right

        if smallest != i:
            self.arr[smallest], self.arr[i] = self.arr[i], self.arr[smallest]
            self.heapify(smallest)

    def heappop(self):
        n = len(self.arr)
        if n == 0:
            return None
        elif n == 1:
            item = self.arr.pop()
        else:
            item = self.arr[0]
            self.arr[0] = self.arr.pop()
            self.heapify(0)

        return item

Reference

本文主要参考《算法导论》。