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; } }
总结
以上就是本文关于java编程实现优先队列的二叉堆代码分享的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站:java集合中list的用法代码示例、Java编程接口调用的作用及代码分享、java并发学习之BlockingQueue实现生产者消费者详解等,有什么问题可以随时留言,小编会及时回复大家的。感谢朋友们对本站的支持!
本文标题:java编程实现优先队列的二叉堆代码分享
文章出自:http://scyanting.com/article/jdispo.html