首页 > 代码库 > java基础之:堆排序

java基础之:堆排序

  最近做题目饱受打击,愈发觉得打好基础的重要性,于是乎,决心把基本的排序算法还有数组操作一一实现,目的在于
一方面能够得到对JAVA基础的巩固,另一面在实现的过程中发现不足。
  今天所实现的堆排序(最大堆)算法,最小堆大同小异。然后基于最大堆实现最大优先队列,最大优先队列可应用于作
业调度,比如可将作业长度作为关键字值,实现最长作业优先;或者将作业优先权值作为关键字值,实现高优先权作业优先
执行等等。
最大堆排序算法结构如下图:

  

 1 //:ThinkingInJava/com.mindview.fundamental/MaxHeap.java 2 package com.mindview.fundamental; 3 /** 4  *  5  * @Time 2014-6-17 6  * @Descri MaxHeap.java 最大堆排序实现算法 7  *             parent (i-1)/2 8  *             left 2*i+1 9  *             right 2*i+210  * @author pattywgm11  *12  */13 public class MaxHeap {14     int a[];15     int a_heapsize;16     //接受数组17     public MaxHeap(int a[]) {18         this.a=a;19         a_heapsize=a.length;20     }21     22     //堆排序23     public void heapSort(){24         buildMaxHeap();25         for(int i=a.length-1;i>0;i--){26             //从大到小输出,实际数组顺序输出为从小到大27 //            System.out.print(a[0]+"  ");28             exchange(0, i);29             a_heapsize=a_heapsize-1;30             maxHeapIFY(0);//from top to bottom31         }32     }33     34     //创建堆35     public void buildMaxHeap(){36         //a[(a.length-1)/2] to a[0] is not leaf37         for(int i=(a.length/2-1);i>=0;i--){38             maxHeapIFY(i);39         }40     }41     //调整堆,以使其符合最大堆性质42     public void maxHeapIFY( int i) {43         int aLeft=2*i+1;//leftChild44         int aRight=2*i+2;//rightChild45         int largest;46         if(aLeft<a_heapsize && a[aLeft]>a[i])47             largest=aLeft;48         else49             largest=i;50         if(aRight<a_heapsize && a[aRight]>a[largest])51             largest=aRight;52         if(largest!=i){53             exchange(i,largest);54             //子树可能违反最大堆性质,继续调整55             maxHeapIFY(largest);56         }57         58         59     }60     //exchange A[i] with A[largest]61     public void exchange(int i, int largest) {62         int temp=a[i];63         a[i]=a[largest];64         a[largest]=temp;65         66     }67 }68 69 ///:~
View Code

  其中buildMaxHeap()实现建立最大堆,HeapSort()方法首先调用该方法建立最大堆,然后获取堆顶元素即为最大元素,
将其与堆底最后一个元素交换后输出到数组中,此时得到新的堆大小,并通过maxHeapIFY()方法继续调整堆,以使堆能够
满足最大堆性质。循环迭代该过程,即可实现最大堆的排序,数组中最后保存的元素顺序是从小到大的。
最大优先队列算法结构图如下:

 1 //:ThinkingInJava/com.mindview.fundamental/MaxPriorityQueue.java 2 package com.mindview.fundamental; 3 /** 4  *  5  * @Time 2014-6-17 6  * @Descri MaxPriorityQueue.java 7  *            基于最大堆,实现最大优先队列,最大优先队列应用于作业调度 8  *           可将作业长度作为关键字,进行比较 9  * @author pattywgm10  *11  */12 public class MaxPriorityQueue {13     int task[];14     MaxHeap heap;15     public MaxPriorityQueue(int[] task) {16         this.task=task;17         heap=new MaxHeap(task);18         heap.buildMaxHeap();//创建最大堆19     }20     //获取最大关键字21     public int heapMaxiMum(){22         return task[0];23     }24     //去掉并返回最大关键字25     public int heapExtractMax(){26         if(heap.a_heapsize<1){27             System.out.println("Error:heap underflow");28             return -1;29         }30         else{31             int max=task[0];32             task[0]=task[heap.a_heapsize-1];33             heap.a_heapsize=heap.a_heapsize-1;34             heap.maxHeapIFY(0);35             return max;36         }37     }38     //在堆中插入元素x39     public void heapInsert(int x){40         task[heap.a_heapsize]=-1;41         System.out.println("insert: "+heap.a_heapsize);42         heap.a_heapsize=heap.a_heapsize+1;43         if(heap.a_heapsize>task.length){44             System.out.println("Error:array overflow");45             return;46         }47         else{48             heapIncreaseKey(heap.a_heapsize-1,x);49         }50     }51     //将元素x值增加到key52     public void heapIncreaseKey(int i,int key){53         if(task[i]>=key){54             System.out.println("new key is not bigger than current key");55             return;56         }57         else{58             task[i]=key;59             //parent: (i-1)/260             while(i>0 && task[(i-1)/2]<task[i]){61                 heap.exchange(i, (i-1)/2);62                 i=(i-1)/2;63             }64         }65     }66     67     public void print(){68         for(int i=0;i<heap.a_heapsize;i++){69             System.out.print(task[i]+"  ");70         }71     }72     73 }74 75 ///:~
View Code

 

  初始化调用MaxHeap类的buildMaxHeap()实现建立最大堆,即初始的最大优先队列。该最大优先队列支持以下操作:
    1)heapMaxiMum():获取最大关键字值(依据最大堆性质,实际上只是获取堆顶元素)
    2)heapExtractMax():去掉并返回最大关键字值,此时应注意重新调整堆(包括堆的大小和重新排列)
    3)heapInsert(key):在现有队列中插入元素key,该操作与4)结合实现
    4) heapIncreaseKey(i,key):将队列中指定位置处的值增加到key,注意值增加后堆性质的满足与否并做出相
    应调整
  映射到作业调度的问题,可将作业优先权值作为关键字值,1)或 2)操作获取当前作业队列中具有最高优先权的作业
进行调度, 2)操作更符合实际情况,在调度的同时更新队列;3)操作当有新的作业到来时将其插入优先权队列,并遵守
最大优先权最先执行的原则;4)操作在作业执行过程中,可能某个在优先权队列中的作业急需被调用,而其当前优先权却
不高,那么就需要提高其优先权,以使其能够被尽早调度。