堆排序

发表于 | 分类于

指标

时间复杂度 O(logn)
空间复杂度O(n)

堆

是脑海中的结构

我们进行堆排序的时候，其实并不是真的要用到二叉树（完全二叉树），而知识借用这个知识来理解，可以将一个数组想象成一棵树

堆分为大根堆和小根堆

  • 大根堆就是所有的根节点都比他的子节点都要大
  • 小根堆就是所有的根节点都比他的子节点都要小

父子树节点关系

由于堆是完全二叉树

  • 父i => 左子树2i+1，右子树2i+2
  • 子树 i => 父节点（i-1）/2

构建和维护堆

heapInsert

  • 用途
    已经有堆，要加新的节点进堆
  • 做法
    向上（父）依次比对：刚进来的i位置的数与他的父节点比较，如果大于父节点就交换，然后i位置变成了他的父节点的位置，然后再比较i位置与他的父节点大小，如此类推
  • 步骤
    1. 将数组的0到1位置的数变成一个大根堆
    2. 然后加入2位置的数
    3. 如此类推
1
2
3
4
while (arr[index] > arr[(index - 1) / 2]) {//边界arr[o]>arr[0]不成立
    swap(arr, index, (index - 1) / 2);
    index = (index - 1) / 2;
}

heapify

  • 用途
    已经有堆，节点的值发生变化
  • 做法
    向下（子）依次比对：i位置的数与他的两个子节点中比较大的值交换，然后i也变成他的大的子节点的位置，然后再与子节点比较，如此类推，堆就调整好了。
  • 步骤
1
2
3
4
5
6
7
8
9
10
11
int left = index * 2 + 1;
while (left < size) {
	int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;
	largest = arr[largest] > arr[index] ? largest : index;
		if (largest == index) {
		  break;
		}
		swap(arr, largest, index);
		index = largest;
		left = index * 2 + 1;
}
  • size是堆的大小，堆可能只是数组的一部分，最大是数组大小

堆排序

1.建堆
堆排序首先是把数组中的所有数，建成一个大小为n的大根堆，堆顶是所有元素中的最大值
2.换位置，缩小堆范围
把堆顶与第n-1位置的元素进行交换，剥离出整个堆结构，放在数组最后的位置

  1. 调整堆
  • 接下来再把n-1大小的堆，从堆顶位置开始，进行大根堆的调整
  • 再把堆顶元素与第n-2位置的元素进行交换，放在数组的最后位置，作为数组的有序部分
  • 依次进行，当堆的大小为1的时候，整个数组就变得有序了

完整代码

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
54
55
56
57
58
59
60
61
62
63
64
public class HeapSort {

	public static void heapSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		for (int i = 0; i < arr.length; i++) {
			heapInsert(arr, i);
		}
		int size = arr.length;
		swap(arr, 0, --size);
		while (size > 0) {
			heapify(arr, 0, size);
			swap(arr, 0, --size);
		}
	}

	public static void heapInsert(int[] arr, int index) {
		while (arr[index] > arr[(index - 1) / 2]) {
			swap(arr, index, (index - 1) / 2);
			index = (index - 1) / 2;
		}
	}

	public static void heapify(int[] arr, int index, int size) {
		int left = index * 2 + 1;
		//size是堆的大小；堆可能只是数组的一部分，最大是数组大小
		while (left < size) {
			//左 右  孩子先比出来一个大的
			//left + 1 < size  右孩子不越界
			int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;
			//父节点加入 比较
			largest = arr[largest] >  arr[index] ? largest : index;
			if (largest == index) {//是自己，不动
				break;
			}
			swap(arr, largest, index);
			index = largest;//父节点下沉
			left = index * 2 + 1;//left下沉
		}
	}

	public static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}

	private static void printArray(int[] arr) {
		if (arr == null) {
			return;
		}
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}

	public static void main(String[] args) {
		int[] arr = new int[] { 3, 5, 4, 2, 6, 7, 1, 9, 8 };
		heapSort(arr);
		printArray(arr);
	}
}

输出

排序后

> >