堆排序

发表于

（二叉）堆是一个数组，它可以被看成一个近似完全二叉树。二叉堆可以分为两种形式：最大堆和最小堆。在最大堆中所有节点的值都大于等于子节点。在最小堆中所有节点的值都小于等于子节点。
其中max_heapify是一个维护最大堆的方法，时间复杂度为O(lgn)，max_heapify是一个建立最大堆的方法。

我们从列表的一半位置开始，如果节点比子节点小则交换位置，如果交换后的子节点比其子节点小继续交换。一直遍历到根节点，这样就建立好了一个最大堆。

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
def parrent_node(index):
    """父节点"""
    return abs(index / 2)


def left_node(index):
    """左子节点"""
    return 2 * index


def right_node(index):
    """右子节点"""
    return 2 * index + 1


def max_heapify(array, index):
    """维护最大堆"""
    left = left_node(index)
    right = right_node(index)
    if left <= len(array) and array[left - 1] > array[index - 1]:
        largest = left
    else:
        largest = index
    if right <= len(array) and array[right - 1] > array[largest - 1]:
        largest = right
    if largest != index:
        array[index - 1], array[largest - 1] = array[largest - 1], array[index - 1]
        max_heapify(array, largest)


def build_max_heap(array):
    """建最大堆"""
    for index in range(len(array) / 2, 0, -1):
        max_heapify(array, index)

执行

1
2
3
4
array = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]
print array
build_max_heap(array)
print array

结果
[4, 1, 3, 2, 16, 9, 10, 14, 8, 7]
[16, 14, 10, 8, 7, 9, 3, 2, 4, 1]