这里主要介绍的是优先队列的二叉堆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编程接口调用的作用及代码分享、java并发学习之blockingqueue实现生产者消费者详解等，有什么问题可以随时留言，小编会及时回复大家的。感谢朋友们对本站的支持！
如对本文有疑问， 点击进行留言回复！！
HashMap、Hashtable、ConcurrentHashMap三者间的异同
解决RecycleView 中Item包含Edittext时，滑动view复用导致数据错乱的问题
多线程、同步工作原理、死锁案例、Lock接口、线程的生命周期的讲解及实现
网友评论