堆排序 Heap-sort

算法

堆排序 heap sort,指的是利用数据结构堆完成排序,排序使用的是最大二叉堆 max heap。

最大二叉堆是一棵完全二叉树,满足如下特征:

  • 从左至右填充。
  • 根节点为最大元素。
  • 除根节点外,所有节点都要小于等于其父节点。

如图所示:

image-20200412200358199

堆不是线性结构,但通常可以用数组进行表示,因为堆每个节点的索引很容易计算,给定一个节点索引 i,很容易计算出其父节点、左子节点和右子节点的索引:

  • 父节点:i / 2i >> 1
  • 左子节点:i * 2i << 1
  • 右子节点:i * 2 + 1i << 1 + 1

以上最大堆,可以使用下面的数组表示:

image-20200412200722467

堆排序最关键的步骤是将数组序列最大堆化,思路是提供功能给定一个节点索引,可以将该索引对应的节点及其子节点维护为满足最大堆的性质,该操作称为最大堆化,是一个递归的操作,思路是:

  • 假定 i 的左右子节点都满足最大堆特性。存在该假定的理由是我们是从叶子节点向根节点进行最大堆化的。
  • 找出 i 和 其左右节点三个值中的最大值索引 largest。
  • 若largest == i,说明 i 已经满足最大堆性质,任务完成。
  • 若 largest != i,说明 i 不满足,交换 largest 和 i 的值,然后,递归地对 largest 继续做最大堆化操作。

维护好堆结构后,堆排序就可以基于以上的最大堆完成排序,具体过程是:

  • 先将待排序序列构建为最大堆。此时根元素为最大元素。
  • 再将根元素与最后的元素置换,此时最大元素位于最后元素上,最大元素排序完毕。
  • 之后将除了最后一个元素的前面元素再次构建为最大堆,然后将最大根元素与倒数第二个元素交换。
  • 重复以上步骤,依次将最大元素置换的对应的位置上,直到未排序元素只有1个,排序结束。

编码

go

// 堆排序
func HeapSort(data []int) {
	// 构建最大堆
	BuildMaxHeap(data)
	// 控制满足最大堆元素个数
	size := len(data)
	// 依次获取最大元素,放在序列后
	for i:=len(data)-1; i>=1; i-- {
		// 交换根节点和当前元素
		data[i], data[0] = data[0], data[i]
		// 最大堆尺寸-1,后边元素已经排序完成
		size -= 1
		// 交换元素后,重新最大堆化
		maxHeapfy(data, 0, size)
	}
}
// 构建最大堆
func BuildMaxHeap(data []int) {
	// 从第一个具有子节点的节点开始构建
	l := len(data)
	for i:=l/2; i>=0; i-- {
		// 维护 i 节点最大堆
		maxHeapfy(data, i, l)
	}
}

// 维护 i 节点的最大堆性质
// size 是最后一个对元素索引
func maxHeapfy(data []int, i, size int) {
	// 确定左右子节点索引
	l, r := i<<1, i<<1 + 1
	// 判断最大值位于哪个索引
	largest := i
	if l < size && data[l] > data[largest] {
		largest = l
	}
	if r < size && data[r] > data[largest] {
		largest = r
	}
	// 若索引 i 不是最大值
	if i != largest {
		// 则交换 i 和 largest 索引元素
		data[i], data[largest] = data[largest], data[i]
		// 递归维护 largest 元素的最大堆性质
		maxHeapfy(data, largest, size)
	}
}

// 测试通过
data := []int{5, 3, 8, 1, 2, 7, 4, 0, 9, 6}
HeapSort(data)
fmt.Println(data) // [0 1 2 3 4 5 6 7 8 9]

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
48
49
50
51
52
53

Python

# 堆排序
def HeapSort(data):
    # 构建最大堆
    BuildMaxHeap(data)
    size = len(data)
    # 从最后一个元素开始,始终与根元素交换
    for i in range(size-1, 0, -1) :
        data[0], data[i] = data[i], data[0]
        # 将除排序好的后边部分元素外,进行最大堆化
        size -= 1
        maxHeapfy(data, 0, size)
# 构建最大堆
def BuildMaxHeap(data):
    l = len(data)
    # 从l/2至0索引,全部最大堆化 
    for i in range(l>>1, -1, -1):
        maxHeapfy(data, i, l)

# 将某节点及其后代节点最大堆化
def maxHeapfy(data, i, size):
    # 确定左右子节点索引
    l, r = i<<1, (i<<1)+1
    # 找到 i,l,r 中最大的元素
    largest = i
    if l<size and data[l]>data[largest] :
        largest = l
    if r<size and data[r]>data[largest] :
        largest = r
    # 若 i 不是最大元素,i 节点与最大元素节点交换
    # 同时将交换过的节点最大堆化 
    if largest != i :
        data[largest], data[i] = data[i], data[largest]
        maxHeapfy(data, largest, size)

# 测试通过
data = [5, 3, 8, 1, 2, 7, 4, 0, 9, 6]
HeapSort(data)
print(data) 
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
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

JavaScript

// 堆排序
function HeapSort(data) {
    // 构建最大堆
    BuildMaxHeap(data)
    // 从最后一个元素开始,始终与根元素交换
    let size = data.length
    for (let i=size-1; i>0; i--) {
        let t = data[0]
        data[0] = data[i]
        data[i] = t
        // 将除排序好的后边部分元素外,进行最大堆化
        maxHeapfy(data, 0, --size)
    }
}
// 构建最大堆
function BuildMaxHeap(data) {
    let l=data.length
    // 从l/2至0索引,全部最大堆化 
    for (let i=l>>1; i>=0; i--) {
        maxHeapfy(data, i, l)
    }
}
// 将某节点及其后代节点最大堆化
function maxHeapfy(data, i, size) {
    // 确定左右子节点索引
    let l = i<<1, r = (i<<1)+1, largest = i
    // 找到 i,l,r 中最大的元素
    if (l<size && data[l]>data[largest]) {
        largest = l
    }
    if (r<size && data[r]>data[largest]) {
        largest = r
    }
    // 若 i 不是最大元素,i 节点与最大元素节点交换
    // 同时将交换过的节点最大堆化 
    if (largest != i) {
        let t = data[i]
        data[i] = data[largest]
        data[largest] = t
        maxHeapfy(data, largest, size)
    }
}

data = [5, 3, 8, 1, 2, 7, 4, 0, 9, 6]
HeapSort(data)
console.log(data)
// (10) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
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

PHP

// can you help me?
1

分析

堆排序的时间复杂度为 O(nlgn),同样是原址排序,不需要额外的存储空间。除了最大堆,还有最小堆,最小堆通常用来构建优先队列。