0%

堆排序

(二叉)堆是一个数组,它可以被看成一个近似完全二叉树。二叉堆可以分为两种形式:最大堆和最小堆。在最大堆中所有节点的值都大于等于子节点。在最小堆中所有节点的值都小于等于子节点。
其中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]

欢迎关注我的其它发布渠道