java编程实现优先队列的二叉堆代码分享
作者:zhangqi66 时间:2022-11-13 15:32:13
这里主要介绍的是优先队列的二叉堆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
标签:java,算法,二叉堆
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
Java面试题冲刺第二十三天--分布式
2023-09-24 07:30:43
![](https://img.aspxhome.com/file/2023/8/58588_0s.png)
自定义spring mvc的json视图实现思路解析
2023-03-12 12:04:44
发布 Android library 到 Maven 解析
2022-11-01 22:20:13
![](https://img.aspxhome.com/file/2023/9/138979_0s.png)
使用JMX监控Zookeeper状态Java API
2023-05-14 02:27:26
Android需要提升权限的操作方法
2021-07-17 11:25:47
Java中File文件操作类的基础用法
2022-09-28 14:37:03
![](https://img.aspxhome.com/file/2023/2/78922_0s.png)
Android 自定义组件卫星菜单的实现
2023-08-16 21:29:29
![](https://img.aspxhome.com/file/2023/4/113284_0s.jpg)
c# 网址压缩简单实现短网址
2022-10-06 15:37:17
Java实现调用对方http接口得到返回数据
2023-02-27 22:36:29
![](https://img.aspxhome.com/file/2023/7/101777_0s.png)
Android仿支付宝支付从底部弹窗效果
2022-04-30 10:37:13
![](https://img.aspxhome.com/file/2023/7/123307_0s.gif)
C#中的数组用法详解
2021-08-19 14:50:17
![](https://img.aspxhome.com/file/2023/0/84440_0s.png)
浅谈React Native打包apk的坑
2022-07-26 05:44:28
![](https://img.aspxhome.com/file/2023/7/139297_0s.jpg)
servlet3文件上传操作
2023-02-05 18:27:44
Java File类 mkdir 不能创建多层目录的解决
2022-12-01 09:20:18
![](https://img.aspxhome.com/file/2023/3/82383_0s.jpg)
利用flutter实现炫酷的list
2022-08-02 01:15:01
![](https://img.aspxhome.com/file/2023/7/138027_0s.gif)
浅谈Java中几种常见的比较器的实现方法
2022-04-08 19:04:36
Java实现克隆的三种方式实例总结
2021-11-21 15:26:14
![](https://img.aspxhome.com/file/2023/2/76632_0s.png)
IDEA2022中部署Tomcat Web项目的流程分析
2023-02-26 17:19:09
![](https://img.aspxhome.com/file/2023/3/88163_0s.jpg)
读取Java文件到byte数组的三种方法(总结)
2023-08-01 17:19:39
Android RecyclerView选择多个item的实现代码
2022-06-09 10:56:56
![](https://img.aspxhome.com/file/2023/6/117136_0s.jpg)