Java 数据结构与算法系列精讲之二叉堆
作者:我是小白呀 时间:2022-05-14 06:31:15
概述
从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章.
优先队列
优先队列 (Priority Queue) 和队列一样, 是一种先进先出的数据结构. 优先队列中的每个元素有各自的优先级, 优先级最高的元素最先得到服务. 如图:
二叉堆
二叉堆 (Binary Heap) 是一种特殊的堆, 二叉堆具有堆的性质和二叉树的性质. 二叉堆中的任意一节点的值总是大于等于其孩子节点值. 如图:
二叉堆实现
获取索引
// 获取父节点的索引值
public int parent(int index) {
if (index <= 0) {
throw new RuntimeException("Invalid Index");
}
return (index - 1) / 2;
}
// 获取左孩子节点索引
public int leftChild(int index) {
return index * 2 + 1;
}
// 获取右孩子节点索引
public int rightChild(int index) {
return index * 2 + 2;
}
添加元素
// 添加元素
public void add(E e) {
data.add(e);
siftUp(data.size() - 1);
}
siftUp
// siftDown
private void siftDown(int k) {
while (leftChild(k) < data.size()) {
int j = leftChild(k);
if (j + 1 < data.size() && data.get(j + 1).compareTo(data.get(j)) > 0) {
j++;
}
if (data.get(k).compareTo(data.get(j)) >= 0) {
break;
}
Collections.swap(data, k, j);
k = j;
}
}
完整代码
import java.util.ArrayList;
import java.util.Collections;
public class BinaryHeap<E extends Comparable<E>> {
private ArrayList<E> data;
// 无参构造
public BinaryHeap() {
data = new ArrayList<>();
}
// 有参构造
public BinaryHeap(int capacity) {
data = new ArrayList<>(capacity);
}
// 或者元素个数
public int size() {
return data.size();
}
// 判断堆是否为空
public boolean isEmpty() {
return data.isEmpty();
}
// 获取父节点的索引值
public int parent(int index) {
if (index <= 0) {
throw new RuntimeException("Invalid Index");
}
return (index - 1) / 2;
}
// 获取左孩子节点索引
public int leftChild(int index) {
return index * 2 + 1;
}
// 获取右孩子节点索引
public int rightChild(int index) {
return index * 2 + 2;
}
// 添加元素
public void add(E e) {
data.add(e);
siftUp(data.size() - 1);
}
// siftUp
private void siftUp(int k) {
while (k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0) {
Collections.swap(data, k, parent(k));
k = parent(k);
}
}
// siftDown
private void siftDown(int k) {
while (leftChild(k) < data.size()) {
int j = leftChild(k);
if (j + 1 < data.size() && data.get(j + 1).compareTo(data.get(j)) > 0) {
j++;
}
if (data.get(k).compareTo(data.get(j)) >= 0) {
break;
}
Collections.swap(data, k, j);
k = j;
}
}
}
来源:https://iamarookie.blog.csdn.net/article/details/122020449
标签:Java,二叉堆,数据结构
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
解决Mybatis中foreach嵌套使用if标签对象取值的问题
2023-11-23 06:02:02
手把手教你如何获取微信用户openid
2023-11-04 01:01:21
![](https://img.aspxhome.com/file/2023/6/62646_0s.jpg)
分布式医疗挂号系统SpringCache与Redis为数据字典添加缓存
2023-06-28 02:26:55
![](https://img.aspxhome.com/file/2023/5/57405_0s.png)
Java内存模型与JVM运行时数据区的区别详解
2023-11-24 13:29:08
详解java接口(interface)在不同JDK版本中的变化
2022-07-18 03:19:16
IDEA新建springboot项目时未生成pom.xml文件的解决操作
2022-08-22 03:16:31
![](https://img.aspxhome.com/file/2023/8/62518_0s.png)
Android 6.0动态权限申请教程
2023-09-26 16:43:56
Java WebService开源框架CXF详解
2023-12-20 13:02:35
![](https://img.aspxhome.com/file/2023/0/62820_0s.jpg)
java @Value(
2023-10-05 02:54:47
![](https://img.aspxhome.com/file/2023/7/63017_0s.png)
Android完美实现平滑过渡的ViewPager广告条
2023-10-01 13:05:31
![](https://img.aspxhome.com/file/2023/2/87272_0s.jpg)
Java SpringBoot自动装配原理详解
2022-09-08 01:15:09
![](https://img.aspxhome.com/file/2023/0/61610_0s.png)
Spring Boot集成ElasticSearch实现搜索引擎的示例
2021-06-02 05:06:16
![](https://img.aspxhome.com/file/2023/3/63793_0s.png)
java开发之Jdbc分页源码详解
2021-10-28 16:06:48
设计模式在Spring框架中的应用汇总
2023-10-22 19:20:09
浅谈MyBatis3 DynamicSql风格语法使用指南
2023-11-25 13:05:06
IntelliJ IDEA 2020.2正式发布,两点多多总能助你提效
2023-08-30 18:15:18
![](https://img.aspxhome.com/file/2023/2/58082_0s.jpg)
Vs2022环境下安装低版本.net framework的实现步骤
2023-07-04 02:58:12
![](https://img.aspxhome.com/file/2023/8/78988_0s.png)
Spring-Data-JPA整合MySQL和配置的方法
2023-10-29 10:19:41
![](https://img.aspxhome.com/file/2023/4/58734_0s.png)
使用纯Java实现一个WebSSH项目的示例代码
2023-03-11 11:32:20
![](https://img.aspxhome.com/file/2023/8/64148_0s.png)
Spring boot配置文件加解密详解
2023-11-12 00:17:29
![](https://img.aspxhome.com/file/2023/3/59583_0s.jpg)