优先队列

发表于 | 分类于 | 阅读次数:

优先级队列

优先级队列还是一个队列，队列的最大特性仍是先进先出，不过在优先级队列中，数据的出对顺序不是按照先进先出，而是按照优先级来，优先级最高的最先出队。
最大优先级队列，无论入队顺序如何，都是当前最大的元素优先出队。
最小优先级队列，无论入队顺序如何，都是当前最小的元素优先出队。

如何实现优先队列

如何实现一个优先级队列？方法有很对，但是用堆来实现是最直接、最高效的。这是因为，堆和优先级队列非常相似，一个堆就可以看作一个优先级队列。很多时候，它们只是概念上的区分而已。
往优先级队列中插入一个元素，就相当于往堆中插入一个元素；从优先级队列中去除优先级最高的元素，就相当于取出堆顶元素。

优先级队应用场景非常多，比如，哈夫曼编码、图的最短路径、最小生成树算法等等。

下面是两个应用优先级队列的例子。（选自极客时间-王争-数据结构与算法之美）

合并有序小文件

假设我们有100个小文件，每个文件的大小时100MB，每个文件中存储的都是有序的字符串。我们希望将这些100个小文件合并成一个有序的大文件。这里就会用到 优先级队列。

整体思路有点像归并排序中的合并函数。我们从这100个文件中，各取第一个字符，放入数组中，然后比较大小，把最小的那个字符串放入合并后的大文件中，并从数组中删除。

假设，最小的字符串来自于13.txt这个小文件，我们就再从这个小文件取下一个字符串，放到数组中，重新比较大小，并且选择最小的放入合并后的大文件，将它从数组中删除。以此类推，知道所有的文件中的数据都放大文件为止。

这里我们用到数组这种数据结构，来存储从小文件中取出来的字符串。每次从数组中取最小字符串，都需要循环遍历整个数组，这种做法是低效的。

这里就可一个用到优先级队列，也就是说堆。我们将小文件中取出来的字符串放入到小顶堆中，把堆顶的元素，也就是优先级队列队首的元素，就是最小的字符串。讲这个字符串放入到大文件中，并将其从堆中删除，然后再从小文件中去除下一个字符串，放入到堆中。循环这个过程就可以把100个小文件中的数据依次入到大文件中。

删除堆顶数据和往堆中插入数据的时间复杂度都是O(logn)，n表示堆中的数据个数，这里就是100，比原来的数组存储的方式高效多了。

高性能定时器

假设有一个定时器，定时器中维护了很多定时任务，每个任务都设定了一个要触发指向的时间点。定时器美国一个很小的单位时间（比如1秒），就扫描一边任务，看是否有任务到达设定的执行时间，如果到达就拿出来执行。

但是这样每过1秒就扫描一遍任务列表的做法比较低效，主要原因有两点：第一，任务的约定执行时间离当前时间可能还有很久，这样前面很多次扫描其实都是徒劳的；第二，每次都要扫描整个任务列表，如果任务列表很大的话，势必会比较耗时。

针对这些问题，就可以用优先级队列来解决。我们按照任务设定的执行时间，将这些任务存储在优先级队列中，队列首部(也就是小顶堆的堆顶)存储的是最先执行的任务。

这样，定时器就不需要每隔1秒就扫描一遍任务列表了。拿队首任务的执行时间点，与当前时间点相减，得到一个时间间隔T。

这个时间间隔T就是，从当前时间开始，需要等待多久，才会有第一个任务需要被执行。这样，定时器就可以设定在T秒之后，再来执行任务。从当前时间点到(T-1)秒时间里，定时器都不需要做任何事情。

当T秒时间过后，定时器取优先级队列中投队首的任务执行。然后再计算新的队首任务的执行时间点与当前时间点的差值，把这个值设置为定时器执行I行啊一个任务需要等待的时间。

这样，定时器既不用间隔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
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

/**
 * @description: 最大优先队列，无论入队的顺序如何，都是当前最大的元素优先出队；最小队列，无论入队的顺序如何，都是当前最小的元素优先出队。
 * @author: rhsphere
 * @since: 2019-07-08 09:34 by jdk 1.8
 */


public class PriorityQueue {
	//使用最大堆来实现最大优先队列，入队就是堆的插入，出队就是堆的删除
	private int[] arr;  //存储元素的数组
	private int size;   //队列中元素的个数
	public PriorityQueue() {
		arr = new int[32];  //队列初始长度为32
	}

	//入队
	public void enQueue(int key) {
		//队列长度超出范围，扩容
		if(size >= arr.length) {
			resize();
		}
		arr[size++] = key;
		upAdjust();
	}

	//出队
	public int deQueue() throws Exception {
		if (size <= 0)
			throw new Exception("the queue is empty");
		//获取堆顶元素
		int head = arr[0];
		//让最后一个元素移到堆顶
		arr[0] = arr[--size];
		downAdjust();
		return head;

	}

	//上浮操作，用于插入的叶子节点，将其移到正确的位置
	private void  upAdjust() {
		int childIndex = size - 1;
		int parentIndex = childIndex / 2;
		int tmp = arr[childIndex];
		while (childIndex > 0 && tmp > arr[parentIndex]) {
			arr[childIndex] = arr[parentIndex];
			childIndex = parentIndex;
			parentIndex = (parentIndex - 1) / 2; //这里需要减一吗
		}
		arr[childIndex] = tmp;
	}

	//下沉操作，用于删除队头元素，并且将最后一个元素放到队头并调整堆的形状
	private void downAdjust() {
		int parentIndex = 0;
		//tmp用于保存父节点的值，用于最后的赋值
		int tmp = arr[parentIndex];
		int childIndex = 1;
		while (childIndex < size) {
			//如果有有孩子且右孩子大于左孩子的值，则定位到右孩子
			if (childIndex + 1 < size && arr[childIndex + 1] > arr[childIndex])
				childIndex++;
			//如果父节点大于左右孩子最大的值，直接跳出
			if (tmp >= arr[childIndex])
				break;
			//较大子节点单向赋值给父节点即可
			arr[parentIndex] = arr[childIndex];
			parentIndex = childIndex;
			childIndex = 2 * childIndex + 1;
		}
		arr[parentIndex] = tmp;
	}
	//扩容
	private void resize() {
		int newSize = this.size * 2;
		this.arr = Arrays.copyOf(this.arr, newSize);
	}

    public static void main(String[] args) throws Exception {
        PriorityQueue pq = new PriorityQueue();
        pq.enQueue(1);
        pq.enQueue(3);
        pq.enQueue(5);
        pq.enQueue(10);
        pq.enQueue(2);
        pq.enQueue(7);
        System.out.println("出队元素：" + pq.deQueue());
        System.out.println("出队元素：" + pq.deQueue());
    }
}

总结

优先队列是一种特殊的队列，优先级高的数据先出队，而不再像普通的队列那样，先进先出。
实际上，堆就可以看作优先级队列，只是称谓不一样。

0%