java编程实现优先队列的二叉堆代码分享

这里主要介绍的是优先队列的二叉堆Java实现，代码如下：

package practice;
import edu.princeton.cs.algs4.StdRandom;
public class TestMain {
 public static void main(String[] args) {
   int[] a = new int[20];
   for (int i = 0; i < a.length; i++) {
     int temp = (int)(StdRandom.random()*100);
     a[i] = temp;
   }
   for (int i : a) {
     System.out.print(i+" ");
   }
   System.out.println();
   PQHeap pq = new PQHeap();
   for (int i = 0; i < 20; i++) {
     pq.insert(a[i]);
   }
   System.out.println();
   for (int i = 0; i < 20; i++) {
     System.out.print(pq.delMax()+" ");
   }
 }
}
/*
* 优先队列的堆实现
* 二叉堆，每个元素有两个子元素，两个子元素均比自己小
*/
class PQHeap{
 private int[] a;
 private int p = 1;
 public PQHeap() {
   a = new int[2];
 }
 /*
  * 插入元素
  */
 public void insert(int elements) {
   if (p == a.length) { resize(a.length*2); }
   a[p++] = elements;
   swim(p - 1); //将刚插入的元素上浮到正确位置
 }
 /*
  * 返回并删除最大元素
  */
 public int delMax() {
   if (p == a.length/4) { resize(a.length/2); }
   int result = a[1]; //找出最大元素
   exch(1, --p); //将最后一个元素移到顶端
   a[p] = 0;
   sink(1); //将刚移上去的元素沉下去，使堆有序
   return result;
 }
 public boolean isEmpty() {
   return p == 0;
 }
 public int size() {
   return p;
 }
 public void show() {
   for (int i : a) {
     System.out.print(i+" ");
   }
   System.out.println();
 }
 /*
  * 上浮元素
  */
 private void swim(int k) { //将元素与父元素比较，比父元素大则换位置
   while (k > 1 && a[k/2] < a[k]) {
     exch(k/2, k);
     k = k/2;
   }
 }
 private void sink(int k) { //将元素与子元素比较，比子元素小则和两个中较大的那个换位置
   while (2*k < p && (a[k] < a[2*k + 1]) || (a[k] < a[2*k])) {
     if (a[2*k + 1] > a[2*k]) { exch(k, 2*k + 1); k = 2*k + 1; }
     else           { exch(k, 2*k); k = 2*k; }
   }
 }
 private void resize(int length) {
   int[] b = new int[length]; //将数组长度改变
   for (int i = 0; i < p; i++) { //将数组复制
     b[i] = a[i];
   }
   a = b; //让a指向b的内存空间
 }
 /*
  * 交换
  */
 private void exch (int i, int j) {
   int t = a[i];
   a[i] = a[j];
   a[j] = t;
 }
}

来源：http://www.cnblogs.com/zhangqi66/p/7245557.html