【Java 数据结构 算法】宁可累死自己, 也要卷死别人 13 二叉堆

概述

从今天开始, 小白我将带大家开启 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);}// 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;}}
}