/**
* 最大优先级队列，例如：在一台分时计算机上进行作业高度。这种队列对要执行的各作业及它们之间的相对优先关系加以记录
* 当一个作业做完或被中断时，用extractMax操作从所有等待的作业中，选择出具有最高优先级的作业；一个新作业则可以调用insert加入队列
*/
public class PriorQueue {
int heapSize = 0;
/**
* 返回arr中最大关键字的元素，并在堆中删除，然后重新调整成最大堆
* @param arr
*/
int extractMax(int arr[]){
if(heapSize<1)
System.out.println("");
int max = arr[0];
arr[0] = arr[heapSize-1];
heapSize--;
//调用堆排序(HeapSort)中的方法把堆重新调整为最大堆
maxHeap(arr,1,heapSize);
return max;
}
/**
* 将堆中i位置的关键字增加到key，这里的key不能小于i位置原来的关键字大小
* @param arr
* @param i
* @param key
*/
void increaseKey(int arr[],int i,int key){
if(key<arr[i-1])
System.out.println("");
arr[i-1] = key;
while(i>1&&arr[i/2-1]<arr[i-1]){
int temp = arr[i/2-1];
arr[i/2-1] = arr[i-1];
arr[i-1] = temp;
i = i/2;
}
}
/**
* 向堆中插入一个新的元素key
* @param arr
* @param key
*/
void insert(int arr[],int key){
this.heapSize++;
arr[heapSize-1] = Integer.MIN_VALUE;
this.increaseKey(arr, heapSize, key);
}
//把堆重新调整为最大堆
void maxHeap(int arr[],int i,int heapsize){
int largest = i;
int p = 2*i;
int q = 2*i + 1;
//由于i和heapsize都是指的元素在堆中的位置而非在数组中的位置，所以涉及到数组操作时都要减1
if(p<=heapsize&&arr[p-1]>arr[largest-1])
largest = p;
if(q<=heapsize&&arr[q-1]>arr[largest-1])
largest = q;
if(largest!=i){
int temp = arr[i-1];
arr[i-1]=arr[largest-1];
arr[largest-1]=temp;
//尽管i的左右孩子已经是最大堆，但是当前面的调整发生以后，其左右孩子就有可能不再是最大堆了，所以要重新调整成最大堆
maxHeap(arr,largest,heapsize);
}
}
//测试.....
public static void main(String[] args) {
int arr[]=new int[20];
PriorQueue prior = new PriorQueue();
for(int i =1;i<16;i++ )
prior.insert(arr, i);
for(int j =0;j<prior.heapSize;j++)
System.out.println(arr[j]);
for(int j = 1;j<6;j++)
System.out.println(prior.extractMax(arr));
prior.increaseKey(arr, 2, 20);
System.out.println(prior.extractMax(arr));
}
}
