前言
在上一篇中简单介绍了二叉堆和优先队列的概念，说明了二叉堆是使用一颗完全二叉树来实现的，并且在插入元素和删除元素的时候一直维持堆化。优先队列利用二叉堆的特点完成了最高优先级最先出列的能力。
二叉堆的实现
1 定义存储结构
根据二叉堆的特性，二叉堆是一个完全二叉树，那么我们可以通过数组来存储二叉堆的元素，好处在没有显式创建指针的情况下也可以迅速找到一个节点的父节点和左右子节点。
private T[] values;
private int count;
// 构造函数,初始化是决定堆大小
public BinaryHeap(int capacity) {
this.values = (T[]) new Comparable[capacity + 1];
}
大家可能注意到了，在初始化的时候我们构建了一个容量为capacity + 1的数组，这事因为我们要弃用下标0的位置，用1当做根节点，这样在计算下标时更好处理。
此外，数组里存放的是继承了Comparable接口的元素，因为元素必须要能比较，才能将集合堆化。
2 寻找父节点及左右子节点
完全二叉树的好处就是除了最下层，每层的元素都是满的，每层的元素都是上一层的两倍，所以获取父节点和左右节点的方式也变得异常简单
/**
* 获取target的父节点下标
*
* @param target
* @return
*/
private int parent(int target) {
return target / 2;
}
/**
* 获取target的左节点下标
*
* @param target
* @return
*/
private int left(int target) {
return target * 2;
}
/**
* 获取target的右节点下标
*
* @param target
* @return
*/
private int right(int target) {
return target * 2 + 1;
}
3 交换元素&比较大小
再说明上浮和下沉之前，还需要最基本的两个方法是比较大小和交换元素
比较大小
/**
* 比较两节点大小
* @param index1
* @param index2
* @return
*/
private boolean less(int index1, int index2) {
// 返回index1的值是否比index2的值小
return values[index1].compareTo(index2) < 0;
}
交换元素
/**
* 交换两节点位置
* @param index1
* @param index2
*/
private void exchange(int index1, int index2) {
T tmp = values[index1];
values[index1] = values[index2];
values[index2] = values[1];
}
4 上浮&下沉
到了二叉堆的两个核心方法了，上浮就是一路往上走，遇到比自己大的就停下来，下沉就是一路往下走，只要下面有比自己大的，就继续往下沉。
/**
* 上浮
* @param target
*/
private void up(int target) {
// target = 1 时代表到了堆顶,不再交换
// 与父节点比较,直到一个比自己大的父节点
while (target > 1 && less(parent(target), target)) {
exchange(parent(target), target);
}
}
/**
* 下沉
* @param target
*/
private void down(int target) {
// 判断是否已经到了堆底
while (left(target) <= count) {
// 找到左右节点的较大节点
int larger = left(target);
if (right(target)<= count && less(larger,right(target))) {
larger = right(target);
}
// 和左右子节点中较大的比较,如果比较大的大,就不需要下沉了
if (less(larger,target)) {
return;
}
// 与较大的子节点交换位置
exchange(larger,target);
// 更新要比较的目标节点坐标
target = larger;
}
}
5 向堆中添加一个元素
向堆中添加元素的思想，就是在堆底（数组最后一个不为null的元素后面），然后上浮
/**
* 插入元素
* @param target
*/
public void insert(T target) {
// 将新元素添加在最后
values[++count] = target;
// 上浮新插入的元素
up(count);
}
6 取出堆顶元素
取出堆顶元素的思想是将堆顶元素和堆底元素进行交换，然后下沉堆底元素，最后回归稳定
/**
* 取出堆顶元素
* @return
*/
public T pop() {
// 先取出堆顶元素
T result = values[1];
// 和堆底元素进行交换
exchange(1,count);
// 清除堆顶元素(此时堆顶元素在堆底)
values[count--] = null;
// 将新插入的元素进行下沉
down(1);
return result;
}
7 二叉堆完整代码
class BinaryHeap<T extends Comparable> {
// 用数组作为二叉堆的底层存储结构
private T[] values;
// 当前二叉堆实际存储的元素数量
private int count;
// 构造函数,初始化是决定堆大小
public BinaryHeap(int capacity) {
this.values = (T[]) new Comparable[capacity + 1];
}
/**
* 取出堆顶元素
* @return
*/
public T pop() {
// 先取出堆顶元素
T result = values[1];
// 和堆底元素进行交换
exchange(1,count);
// 清除堆顶元素(此时堆顶元素在堆底)
values[count--] = null;
// 将新插入的元素进行下沉
down(1);
return result;
}
/**
* 插入元素
* @param target
*/
public void insert(T target) {
// 将新元素添加在最后
values[++count] = target;
// 上浮新插入的元素
up(count);
}
/**
* 获取target的父节点下标
*
* @param target
* @return
*/
private int parent(int target) {
return target / 2;
}
/**
* 获取target的左节点下标
*
* @param target
* @return
*/
private int left(int target) {
return target * 2;
}
/**
* 获取target的右节点下标
*
* @param target
* @return
*/
private int right(int target) {
return target * 2 + 1;
}
/**
* 上浮
* @param target
*/
private void up(int target) {
// target = 1 时代表到了堆顶,不再交换
// 与父节点比较,直到一个比自己大的父节点
while (target > 1 && less(parent(target), target)) {
exchange(parent(target), target);
}
}
/**
* 下沉
* @param target
*/
private void down(int target) {
// 判断是否已经到了堆底
while (left(target) <= count) {
// 找到左右节点的较大节点
int larger = left(target);
if (right(target)<= count && less(larger,right(target))) {
larger = right(target);
}
// 和左右子节点中较大的比较,如果比较大的大,就不需要下沉了
if (less(larger,target)) {
return;
}
// 与较大的子节点交换位置
exchange(larger,target);
// 更新要比较的目标节点坐标
target = larger;
}
}
/**
* 交换两节点位置
* @param index1
* @param index2
*/
private void exchange(int index1, int index2) {
T tmp = values[index1];
values[index1] = values[index2];
values[index2] = values[1];
}
/**
* 比较两节点大小
* @param index1
* @param index2
* @return
*/
private boolean less(int index1, int index2) {
// 返回index1的值是否比index2的值小
return values[index1].compareTo(index2) < 0;
}
}
优先队列的实现
有了二叉堆，优先队列就特别简单了，直接看代码
class PriorityQueue<T extends Comparable> {
private BinaryHeap<T> binaryHeap;
public PriorityQueue(int capacity) {
this.binaryHeap = new BinaryHeap(capacity);
}
public void push(T t) {
this.binaryHeap.insert(t);
}
public T pop(){
return this.binaryHeap.pop();
}
}
以上就是二叉堆和优先队列的实现，下一篇会结合二叉堆和优先队列完成洗衣机问题。
邀请日更小伙伴
最近一直在持续日更，所以组织了一个群，欢迎小伙伴一起加入，进群方式私信我~
网友评论