/** * 最大优先级队列,例如:在一台分时计算机上进行作业高度。这种队列对要执行的各作业及它们之间的相对优先关系加以记录 * 当一个作业做完或被中断时,用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)); } }