堆和优先队列
程序员文章站
2024-02-15 21:47:52
...
什么是优先队列
为什么会使用优先队列
动态:
任务处理中心随时都在处理各种各样的请求,也就是说不是一开始就确定了各种请求的优先级的,请求的优先级是不断地变化的。
堆的基本结构
堆其实也是一棵树。
二叉堆的性质 :
首先是一个完全二叉树
堆中某个节点的值总是不大于其父节点的值 ---->最大堆
数组实现最大堆
package MaxHeap;
public class MaxHeap<E extends Comparable<E>> {
private Array<E> data;
public MaxHeap(int capacity) {
data = new Array<>(capacity);
}
public MaxHeap() {
data = new Array<>();
}
// 返回堆中的元素个数
public int size() {
return data.getSize();
}
// 返回一个布尔值, 表示堆中是否为空
public boolean isEmpty() {
return data.isEmpty();
}
// 返回完全二叉树的数组表示中,一个索引所表示的元素的父亲节点的索引
private int parent(int index) {
if (index == 0)
throw new IllegalArgumentException("index-0 doesn't have parent.");
return (index - 1) / 2;
}
// 返回完全二叉树的数组表示中,一个索引所表示的元素的左孩子节点的索引
private int leftChild(int index) {
return index * 2 + 1;
}
// 返回完全二叉树的数组表示中,一个索引所表示的元素的右孩子节点的索引
private int rightChild(int index) {
return index * 2 + 2;
}
}
上一篇: 优先队列和堆
下一篇: 如何优雅的生成接口文档?