堆（Heap）

Posted on | In

注意本文说的堆是数据结构中的堆，而不是java内存模型中的堆。

一、定义

n个元素的序列{k1, k2, …, kn}当且仅当满足ki<=k2i, ki<=k2i+1或ki>=k2i, ki>=k2i+1(i=1,2,3,..,n/2向下取整),关系时，称之为堆。若堆顶元素最小，则称之为小顶堆或小根堆。若堆顶元素最大，则称之为大顶堆或大根堆。如下图所示。

二、性质

若以一维数组作为堆的存储结构，并将该一维数组看成是一个完全二叉树，则完全二叉树中所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值。

堆顶元素（或完全二叉树的根）是堆中最小值（或最大值）。

最后一个非终端结点是第n/2向下取整个元素。

三、操作

  • 向上移动

向上移动又有人称其为上浮，是将一个元素与其父结点比较大小，不符合堆的条件就交换位置，交换后继续与新的父结点比较，如此循环，直到符合堆的条件为止。如上图所示，如果是小根堆，而该元素却小于父结点，那么就需要将其向上移动，移动后再与新的父结点比较，以此类推，直到找到某个位置，它不再小于父结点，则该满足堆的条件，移动结束。

参考代码：

1
2
3
4
5
6
private void shiftUp(int k) {
	while(parent(k) >= 0 && _heap[k] < _heap[parent(k)]) {
		swap(k, parent(k));
		k = parent(k);
	}
}

  • 向下移动

向下移动又有人称其为下沉，是将一个元素与其孩子结点进行比较与调整。如上图所示，如果是小根堆，用该结点与其左右孩子中较小的一个结点比较，如果大于那个孩子，则与其交换，交换后继续与新的孩子结点比较，以此类堆，直到找到其合适位置为止。

参考代码：

1
2
3
4
5
6
7
8
9
private void shiftDown(int k) {
	while(left(k) < _heapSize) {
		int j = left(k);
		if(right(k) < _heapSize && _heap[right(k)] < _heap[left(k)]) j++;
		if(_heap[k] < _heap[j]) break;
		swap(k,j);
		k = j;
	}
}

  • 插入

插入也就是向堆中加入新成员的操作。那么新成员放在哪里呢？放在最后。那放在最后是不是可能破坏堆的结构啊？没错。怎么办？将其向上移动。

参考代码：

1
2
3
4
5
6
public void insert(int v) {
	if(_heapSize >= _maxSize) return; //如超出容量，这里只简单地返回，实际中请根据需求进行处理
	_heap[_heapSize] = v;
	shiftUp(_heapSize);
	_heapSize++;
}

  • 删除

删除也就是堆顶元素被拿走了。群龙无首这下怎么办？别急我们要选出新的堆顶。下面我来告诉你怎么办，首先把堆中最后一个元素搬到堆顶，然后将其向下移动。对，就这么简单。

参考代码：

1
2
3
4
5
6
7
8
9
10
public int delMin() throws Exception {
	if(_heapSize == 0) {
		throw new Exception("The heap is already empty!");
	}
	int max = _heap[0];
	_heapSize--;
	swap(0, _heapSize);
	shiftDown(0);
	return max;
}

  • 创建

个人理解堆的创建其实就是将一个序例通过某些操作，使其满足堆的条件从而转化为堆的过程。也就是你给我一个序列，我还你一个堆！

那么如何去搞呢？ 有两种方式：

1）逐个插入。插入操作会自觉保证插入后该序列仍然是堆。

参考代码

1
2
3
4
5
6
7
8
9
public MinHeap(int[] initialNums, int maxSize) {
	_maxSize = maxSize;
	_heap = new int[maxSize];

	//请看关键代码，逐个插入
	for(int i = 0; i < initialNums.length; i++) {
		insert(initialNums[i]);
	}
}

2）逐个调整。从最后一个非终端结点开始，向前，逐个调整以各个非终端结点为根的子树，使每棵子树都变成堆，等最后一个非终端结点调整完毕，整个序列就变成了堆。

参考代码

1
2
3
4
5
6
7
8
9
10
public MinHeap(int[] initialNums, int maxSize) {
	_maxSize = maxSize;
	_heap = Arrays.copyOf(initialNums, initialNums.length);
	_heapSize = initialNums.length;
	
	//从最后一个非终端结点开始逐棵子树调整
	for(int i = ((_heapSize - 1) / 2); i >= 0; i--) {
		shiftDown(i);
	}
}

四、完整代码

该代码简单实现了小顶堆的创建、插入、删除等操作。希望能够辅助读者理解。为简单起见，这里只接收int类型数据。


点击查看完整代码

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
package just.doit;
import java.lang.Exception;

public class MinHeap {
	private  int _heapSize = 0;
	private  int _maxSize;
	private  int[] _heap = null;

//	public MinHeap(int[] initialNums, int maxSize) {
//		_maxSize = maxSize;
//		_heap = Arrays.copyOf(initialNums, initialNums.length);
//		_heapSize = initialNums.length;
//		
//		//从最后一个非终端结点开始逐棵子树调整
//		for(int i = ((_heapSize - 1) / 2); i >= 0; i--) {
//			shiftDown(i);
//		}
//	}

	public MinHeap(int[] initialNums, int maxSize) {
		_maxSize = maxSize;
		_heap = new int[maxSize];

		//逐个插入
		for(int i = 0; i < initialNums.length; i++) {
			insert(initialNums[i]);
		}
	}

	public void insert(int v) {
		if(_heapSize >= _maxSize) return; //如超出容量，这里只简单地返回，实际中请根据需求进行处理
		_heap[_heapSize] = v;
		shiftUp(_heapSize);
		_heapSize++;
	}

	public int delMin() throws Exception {
		if(_heapSize == 0) {
			throw new Exception("The heap is already empty!");
		}
		int max = _heap[0];
		_heapSize--;
		swap(0, _heapSize);
		shiftDown(0);
		return max;
	}

	public void printMinHeap() {
		for(int i = 0; i < _heapSize; i++) {
			System.out.print(_heap[i]+" ");
		}
		System.out.println();
	}

	private void shiftUp(int k) {
		while(parent(k) >= 0 && _heap[k] < _heap[parent(k)]) {
			swap(k, parent(k));
			k = parent(k);
		}
	}

	private void shiftDown(int k) {
		while(left(k) < _heapSize) {
			int j = left(k);
			if(right(k) < _heapSize && _heap[right(k)] < _heap[left(k)]) j++;
			if(_heap[k] < _heap[j]) break;
			swap(k,j);
			k = j;
		}
	}

	private void swap(int i, int j) {
		int temp = _heap[i];
		_heap[i] = _heap[j];
		_heap[j] = temp;
	}
	//本代码从0开始存储，所以left为2 * k + 1，若从1开始存储则left为2 * k
	private int left(int k) {
		return 2 * k + 1;
	}
	//本代码从0开始存储，所以right为2 * k + 2，若从1开始存储则right为2 * k + 1
	private int right(int k) {
		return 2 * k + 2;
	}
	//本代码从0开始存储，所以parent为(k - 1) / 2，若从1开始存储则parent为k / 2
	private int parent(int k) {
		return (k - 1) / 2;
	}

	public static void main(String[] args) throws Exception {
		int[] a = {10,33,1,4,3,29,5,8};

		MinHeap maxHeap = new MinHeap(a, 20); //使用逐个插入的方式构建堆

		maxHeap.printMinHeap(); // 1 3 5 8 4 29 10 33

		System.out.println(maxHeap.delMin()); // 取出堆顶元素 1

		maxHeap.printMinHeap(); //取出堆顶元素后的新堆 3 4 5 8 33 29 10

		maxHeap.insert(6); // 插入 6

		maxHeap.printMinHeap(); // 插入后的新堆 3 4 5 6 33 29 10 8
	}

}


五、使用场景

堆的使用场景包括但不限于一下三种。

  • 堆排序

有了上面的基础，堆排序的思路很简单，给一个序列，先将其构建成堆，堆顶元素肯定是最大（或最小值），将堆顶元素放到序列末尾，并把末尾元素补充到堆顶，并对其进行向下调整，调整到n-1位置为止，这样前n-1个元素又是一个堆，又可以取到第二大（或第二小）的值，以此类推，直到堆只剩下一个元素，将得到一个有序序列。

如下代码是通过构建小根堆，将int数组从大到小排序：

1
2
3
4
5
6
7
8
public static void heapSort(int[] initialNums) {
	int[] heap = buildMinHeap(initialNums);

	for(int i = heap.length - 1; i > 0; i--) {
		swap(heap, 0, i);
		shiftDown(heap, 0, i);
	}
}

点击查看完整代码

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

package just.doit;

import java.util.Arrays;

public class Sort {
	public static void heapSort(int[] initialNums) {
		int[] heap = buildMinHeap(initialNums);

		for(int i = heap.length - 1; i > 0; i--) {
			swap(heap, 0, i);
			shiftDown(heap, 0, i);
		}
	}

	private static int[] buildMinHeap(int[] initialNums) {
		for(int i = ((initialNums.length - 1) / 2); i >= 0; i--) {
			shiftDown(initialNums, i, initialNums.length);
		}
		return initialNums;
	}

	private static void shiftDown(int[] heap, int k, int heapSize) {
		while(left(k) < heapSize) {
			int j = left(k);
			if(right(k) < heapSize && heap[right(k)] < heap[left(k)]) j++;
			if(heap[k] < heap[j]) break;
			swap(heap,k,j);
			k = j;
		}
	}

	private static void swap(int[] heap, int i, int j) {
		int temp = heap[i];
		heap[i] = heap[j];
		heap[j] = temp;
	}

	private static int left(int k) {
		return 2 * k + 1;
	}

	private static int right(int k) {
		return 2 * k + 2;
	}

	public static void main(String[] args) {
		int[] a = {5,23,7,33,2,1,16,9};
		System.out.println("排序前：" + Arrays.toString(a));
		Sort.heapSort(a);
		System.out.println("堆排序后：" + Arrays.toString(a));
	}

}

输出：
排序前：[5, 23, 7, 33, 2, 1, 16, 9]
堆排序后：[33, 23, 16, 9, 7, 5, 2, 1]


  • 优先队列

堆可以用来实现优先队列（Priority Queue）。说到队列，大家立刻会想到先进先出。根据名字来看，优先队列似乎不一样。没错，它根据元素的优先级来决定取出顺序。关于优先队列这里不过多讲述。

  • 海量数据中找TopK

例如给了一百万个数据，我想找到最大的100个数据。那么我可以先拿100个元素建一个小根堆，然后一个一个取剩下的元素与堆顶比较，如果大于堆顶，则把堆顶删除，再把这个元素放入堆中。如果小于堆顶，则不做处理。最后堆中100个元素则为最大的100元素。

六、总结

以上则为作者对堆的一些认识与总结，希望能给读者一些启发。如有不妥之处，希望能得到批评指正！

结尾与君共同赏古诗一首，愿君更上一层楼！

      登鹳雀楼  
    [唐] 王之涣  
白日依山尽，黄河入海流。  
欲穷千里目，更上一层楼。

七、参考文献

《数据结构》 严蔚敏 吴伟民 编著
《算法导论》 殷建平 徐云 等译
《算法》 谢路云 译