优先级队列，是堆数据结构的典型应用。优先级队列的一个典型应用，就是排队任务的有限调度，当一个任务结束后，优先执行当前优先级最高的任务。队列一个任务是，调用INSERT方法。
package lhz.algorithm.chapter.six;
/**
* "优先级队列"，《算法导论》6.5章节
* 原文摘要：
* A priority queue is a data structure for maintaining a set S of elements, each with an
* associated value called a key. A max-priority queue supports the following operations.
* ・ INSERT(S, x) inserts the element x into the set S. This operation could be written as S← S{x}.
* ・ MAXIMUM(S) returns the element of S with the largest key.
* ・ EXTRACT-MAX(S) removes and returns the element of S with the largest key.
* ・ INCREASE-KEY(S, x, k) increases the value of element x‘s key to the new value k,
* which is assumed to be at least as large as x‘s current key value.
* 堆的一种实际应用，可用于任务调度队列等。包含四个操作方法。
* @author lihzh(OneCoder)
* @blog http://www.coderli.com
*/
public class PriorityQueue {
private static final int DEFAULT_CAPACITY_VALUE = 16;
//初始化一个长度为16的队列（可作为构造参数)，此处选择16参考HashMap的初始化值
private int[] queue;
//堆大小
private int heapSize = 0;
public static void main(String[] args) {
PriorityQueue q = new PriorityQueue();
q.insert(2);
q.insert(6);
q.insert(3);
q.insert(8);
q.insert(7);
q.insert(9);
q.insert(1);
q.insert(10);
q.insert(9);
System.out.println(q.extractMax());
System.out.println(q.extractMax());
q.insert(9);
q.insert(1);
q.insert(10);
System.out.println(q.extractMax());
System.out.println(q.extractMax());
System.out.println(q.extractMax());
System.out.println(q.extractMax());
System.out.println(q.extractMax());
System.out.println(q.extractMax());
System.out.println(q.extractMax());
}
public PriorityQueue(int capacity) {
this.queue = new int[capacity];
}
public PriorityQueue() {
this(DEFAULT_CAPACITY_VALUE);
}
/**
* 返回当前最大值
* @return
*/
public int maximum() {
return queue[0];
}
/**
* 往优先级队列出，插入一个元素
* 利用INCREASE-Key方法，从堆的最后增加元素
* 伪代码：
* MAX-HEAP-INSERT(A, key)
* 1 heap-size[A] ← heap-size[A] + 1
* 2 A[heap-size[A]] ← -∞
* 3 HEAP-INCREASE-KEY(A, heap-size[A], key)
* 时间复杂度：O(lg n)
* @param value 待插入元素
*/
public void insert(int value) {
//注意堆容量和数组索引的错位 1
queue[heapSize] = value;
heapSize++;
increaceKey(heapSize, value);
}
/**
* 增加给定索引位元素的值，并重新构成MaxHeap。
* 新值必须大于等于原有值
* 伪代码：
* HEAP-INCREASE-KEY(A, i, key)
* 1 if key < A[i]
* 2 then error "new key is smaller than current key"
* 3 A[i] ← key
* 4 while i > 1 and A[PARENT(i)] < A[i]
* 5 do exchange A[i] ↔ A[PARENT(i)]
* 6 i ← PARENT(i)
* 时间复杂度：O(lg n)
* @param index 索引位
* @param newValue 新值
*/
public void increaceKey (int heapIndex, int newValue) {
if (newValue < queue[heapIndex-1]) {
System.err.println("错误：新值小于原有值！");
return;
}
queue[heapIndex-1] = newValue;
int parentIndex = heapIndex / 2;
while (parentIndex > 0 && queue[parentIndex-1] < newValue ) {
int temp = queue[parentIndex-1];
queue[parentIndex-1] = newValue;
queue[heapIndex-1] = temp;
heapIndex = parentIndex;
parentIndex = parentIndex / 2;
}
}
/**
* 返回堆顶元素（最大值），并且将堆顶元素移除
* 伪代码：
* HEAP-EXTRACT-MAX(A)
* 1 if heap-size[A] < 1
* 2 then error "heap underflow"
* 3 max ← A[1]
* 4 A[1] ← A[heap-size[A]]
* 5 heap-size[A] ← heap-size[A] - 1
* 6 MAX-HEAPIFY(A, 1)
* 7 return max
* 时间复杂度：O(lg n),
* @return
*/
public int extractMax() {
if (heapSize < 1) {
System.err.println("堆中已经没有元素!");
return -1;
}
int max = queue[0];
queue[0] = queue[heapSize-1];
heapSize--;
maxHeapify(queue, 1);
return max;
}
/**
* 之前介绍的保持最大堆的算法
* @param array
* @param index
*/
private void maxHeapify(int[] array, int index) {
int l = index * 2;
int r = l + 1;
int largest;
//如果左叶子节点索引小于堆大小，比较当前值和左叶子节点的值，取值大的索引值
if (l <= heapSize && array[l-1] > array[index-1]) {
largest = l;
} else {
largest = index;
}
//如果右叶子节点索引小于堆大小，比较右叶子节点和之前比较得出的较大值，取大的索引值
if (r <= heapSize && array[r-1] > array[largest-1]) {
largest = r;
}
//交换位置，并继续递归调用该方法调整位置。
if (largest != index) {
int temp = array[index-1];
array[index-1] = array[largest-1];
array[largest-1] = temp;
maxHeapify(array, largest);
}
}
public int[] getQueue() {
return queue;
}
}
