算法导论Java实现-优先级队列(6.5章节)

优先级队列，是堆数据结构的典型应用。优先级队列的一个典型应用，就是排队任务的有限调度，当一个任务结束后，优先执行当前优先级最高的任务。队列一个任务是，调用INSERT方法。

1. package lhz.algorithm.chapter.six; 
2. /** 
3.  * “优先级队列”，《算法导论》6.5章节 
4.  * 原文摘要： 
5.  * A priority queue is a data structure for maintaining a set S of elements, each with an 
6.  * associated value called a key. A max-priority queue supports the following operations. 
7.  * • INSERT(S, x) inserts the element x into the set S. This operation could be written as S← S{x}. 
8.  * • MAXIMUM(S) returns the element of S with the largest key. 
9.  * • EXTRACT-MAX(S) removes and returns the element of S with the largest key. 
10.  * • INCREASE-KEY(S, x, k) increases the value of element x's key to the new value k, 
11.  * which is assumed to be at least as large as x's current key value. 
12.  * 堆的一种实际应用，可用于任务调度队列等。包含四个操作方法。 
13. * 原文地址： http://mushiqianmeng.blog.51cto.com/3970029/743611
14.  * @author lihzh(苦逼coder) 
15.  */ 
16. public class PriorityQueue { 
17.      
18.     private final int DEFAULT_CAPACITY_VALUE = 16; 
19.     //初始化一个长度为16的队列（可作为构造参数)，此处选择16参考HashMap的初始化值 
20.     private int capacity = DEFAULT_CAPACITY_VALUE; 
21.     private int[] quene = new int[capacity]; 
22.     //堆大小 
23.     private int heapSize = 0; 
24.  
25.     /** 
26.      * 返回当前最大值 
27.      * @return 
28.      */ 
29.     public int maximum() { 
30.         return quene[0]; 
31.     } 
32.      
33.     /** 
34.      * 往优先级队列出，插入一个元素 
35.      * 利用INCREASE-Key方法，从堆的最后增加元素 
36.      * 伪代码： 
37.      * MAX-HEAP-INSERT(A, key) 
38.      * 1 heap-size[A] ← heap-size[A] + 1 
39.      * 2 A[heap-size[A]] ← -∞ 
40.      * 3 HEAP-INCREASE-KEY(A, heap-size[A], key) 
41. * 时间复杂度：O(lg n) 
42.  
43.      * @param value 待插入元素 
44.      */ 
45.     public void insert(int value) { 
46.         //注意堆容量和数组索引的错位 1 
47.         quene[heapSize] = value; 
48.         heapSize++; 
49.         increaceKey(heapSize, value); 
50.     } 
51.      
52.     /** 
53.      * 增加给定索引位元素的值，并重新构成MaxHeap。 
54.      * 新值必须大于等于原有值 
55.      * 伪代码： 
56.      * HEAP-INCREASE-KEY(A, i, key) 
57.      * 1 if key < A[i] 
58.      * 2 then error "new key is smaller than current key" 
59.      * 3 A[i] ← key 
60.      * 4 while i > 1 and A[PARENT(i)] < A[i] 
61.      * 5 do exchange A[i] ↔ A[PARENT(i)] 
62.      * 6 i ← PARENT(i) 
63.      * 时间复杂度：O(lg n) 
64.      * @param index 索引位 
65.      * @param newValue 新值 
66.      */ 
67.     public void increaceKey (int heapIndex, int newValue) { 
68.         if (newValue < quene[heapIndex-1]) { 
69.             System.err.println("错误：新值小于原有值！"); 
70.             return; 
71.         } 
72.         quene[heapIndex-1] = newValue; 
73.         int parentIndex = heapIndex / 2; 
74.         while (parentIndex > 0 && quene[parentIndex-1] < newValue ) { 
75.             int temp = quene[parentIndex-1]; 
76.             quene[parentIndex-1] = newValue; 
77.             quene[heapIndex-1] = temp; 
78.             heapIndex = parentIndex; 
79.             parentIndex = parentIndex / 2; 
80.         } 
81.     } 
82.      
83.     /** 
84.      * 返回堆顶元素（最大值），并且将堆顶元素移除 
85.      * 伪代码： 
86.      * HEAP-EXTRACT-MAX(A) 
87.      * 1 if heap-size[A] < 1 
88.      * 2 then error "heap underflow" 
89.      * 3 max ← A[1] 
90.      * 4 A[1] ← A[heap-size[A]] 
91.      * 5 heap-size[A] ← heap-size[A] - 1 
92.      * 6 MAX-HEAPIFY(A, 1) 
93.      * 7 return max 
94.      * 时间复杂度：O(lg n), 
95.      * @return 
96.      */ 
97.     public int extractMax() { 
98.         if (heapSize < 1) { 
99.             System.err.println("堆中已经没有元素!"); 
100.             return -1; 
101.         } 
102.         int max = quene[0]; 
103.         quene[0] = quene[heapSize-1]; 
104.         heapSize--; 
105.         maxHeapify(quene, 1); 
106.         return max; 
107.     } 
108.      
109.      
110.     /** 
111.      * 之前介绍的保持最大堆的算法 
112.      * @param array 
113.      * @param index 
114.      */ 
115.     private  void maxHeapify(int[] array, int index) { 
116.         int l = index * 2; 
117.         int r = l + 1; 
118.         int largest; 
119.         //如果左叶子节点索引小于堆大小，比较当前值和左叶子节点的值，取值大的索引值 
120.         if (l <= heapSize && array[l-1] > array[index-1]) { 
121.             largest = l; 
122.         } else { 
123.             largest = index; 
124.         } 
125.         //如果右叶子节点索引小于堆大小，比较右叶子节点和之前比较得出的较大值，取大的索引值 
126.         if (r <= heapSize && array[r-1] > array[largest-1]) { 
127.             largest = r; 
128.         } 
129.         //交换位置，并继续递归调用该方法调整位置。 
130.         if (largest != index) { 
131.             int temp = array[index-1]; 
132.             array[index-1] = array[largest-1]; 
133.             array[largest-1] = temp; 
134.             maxHeapify(array, largest); 
135.         } 
136.     } 
137. } 

简单的测试代码：

1. public static void main(String[] args) { 
2.         PriorityQueue q = new PriorityQueue(); 
3.         q.insert(2); 
4.         q.insert(6); 
5.         q.insert(3); 
6.         q.insert(8); 
7.         q.insert(7); 
8.         q.insert(9); 
9.         q.insert(1); 
10.         q.insert(10); 
11.         q.insert(9); 
12.         System.out.println(q.extractMax()); 
13.         System.out.println(q.extractMax()); 
14.         q.insert(9); 
15.         q.insert(1); 
16.         q.insert(10); 
17.         System.out.println(q.extractMax()); 
18.         System.out.println(q.extractMax()); 
19.         System.out.println(q.extractMax()); 
20.         System.out.println(q.extractMax()); 
21.         System.out.println(q.extractMax()); 
22.         System.out.println(q.extractMax()); 
23.         System.out.println(q.extractMax()); 
24.     } 

     本文转自mushiqianmeng 51CTO博客，原文链接：http://blog.51cto.com/mushiqianmeng/743611，如需转载请自行联系原作者