Java|Java 数据结构与算法系列精讲之二叉堆
目录
- 概述
- 优先队列
- 二叉堆
- 二叉堆实现
- 获取索引
- 添加元素
- siftUp
- 完整代码
概述 从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章.
优先队列 优先队列 (Priority Queue) 和队列一样, 是一种先进先出的数据结构. 优先队列中的每个元素有各自的优先级, 优先级最高的元素最先得到服务. 如图:
![Java|Java 数据结构与算法系列精讲之二叉堆](https://img.it610.com/image/info11/37caa106f2454e2292643b6b7a7910da.gif)
文章图片
二叉堆 二叉堆 (Binary Heap) 是一种特殊的堆, 二叉堆具有堆的性质和二叉树的性质. 二叉堆中的任意一节点的值总是大于等于其孩子节点值. 如图:
![Java|Java 数据结构与算法系列精讲之二叉堆](https://img.it610.com/image/info11/473bcc1d6aad4bac903a0ab3d8da93d3.jpg)
文章图片
二叉堆实现
获取索引
// 获取父节点的索引值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
// siftDownprivate 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> {private ArrayList data; // 无参构造public BinaryHeap() {data = https://www.it610.com/article/new ArrayList<>(); }// 有参构造public BinaryHeap(int capacity) {data = https://www.it610.com/article/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); }// siftUpprivate 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); }}// siftDownprivate 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; }}}
【Java|Java 数据结构与算法系列精讲之二叉堆】到此这篇关于Java 数据结构与算法系列精讲之二叉堆的文章就介绍到这了,更多相关Java 二叉堆内容请搜索脚本之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持脚本之家!
推荐阅读
- Java|Java 超详细讲解数据结构中的堆的应用
- Java|Java ASM使用logback日志级别动态切换方案展示
- Java|Java 数据结构七大排序使用分析
- Javascript中Microtask和Macrotask鲜为人知的知识点
- python|Python【 for循环与while循环】
- 中信建投X袋鼠云(实时数仓,证券机构的“速度与稳定”)
- 【刘建】JavaScript宏任务与微任务的原理解析
- 从重大漏洞应急看云原生架构下的安全建设与安全运营(下)
- Python文件的应用之序列化与反序列化详解
- Java|Java 多层嵌套JSON类型数据全面解析