图解二叉堆
2019-06-04 本文已影响0人
Taonce
二叉堆本质上其实就是一种完全二叉树(不熟悉二叉树的可以看前面的文章：图解二叉树)，它分为两种类型：
-
最大堆：堆中任何一个父节点的值都大于等于它左右子节点的值
-
最小堆：显然和最大堆相反，堆中任何一个父节点的值都小于等于它左右子节点的值
对于一个二叉堆的操作主要包含了两个：插入节点和删除节点；接下来会对这两种操作进行具体的说明，说明的对象都是最小堆，如果理解了最小堆的操作，那么最大堆的操作就易如反掌了。
插入节点 (最小堆)
插入一个节点主要的逻辑就是在二叉树的最后节点上安置新的节点，然后比较此节点和父节点的大小。如果是小于父节点，那么就不用操作，直接生成此二叉堆；如果是大于父节点，那么将此节点和父节点位置互换(也就是上浮操作)，将互换后的父节点作为新的节点，再进行新节点和父节点的大小比较，直到新节点小于父节点或者新节点为根节点，结束。文字的表现力依旧比较复杂，下面就看插入的流程图吧，结合流程图会更加贴切的理解插入过程。
- 在现有的二叉堆 ( 0, 3, 2, 7, 9, 5, 6, 10, 8 ) 中插入新的节点 1
- 新节点与父节点对比，新节点 1 小于 父节点 9，那么就互换位置
- 互换后的节点 1 再与其父节点对比，1 小于其父节点 3，再次互换位置
- 再看此时的新节点 1，对于其现有父节点 0，它是大于其父节点的，所以终止上浮操作，生成最终的二叉堆 ( 0 1 2 7 3 5 6 10 8 9 )，如上图所示。
下面看具体的代码实现：
/**
* 添加一个结点
*
* @param element 结点值
*/
public void addNode(Integer element) {
_data.add(element);
up();
}
/**
* 进行上浮操作
*/
private void up() {
int tempIndex = _data.size() - 1;
int parentIndex = (tempIndex - 1) / 2;
Integer temp = _data.get(tempIndex);
while (tempIndex > 0) {
int cmp = _data.get(parentIndex) - temp;
if (cmp <= 0) {
break;
} else {
_data.set(tempIndex, _data.get(parentIndex));
tempIndex = parentIndex;
parentIndex = (parentIndex - 1) / 2;
}
}
_data.set(tempIndex, temp);
}
删除节点 (最小堆)
删除节点的操作和逻辑要比添加节点稍微复杂那么一丢丢，但是其本质还是一样的，比较子节点和父节点的大小进行下沉操作。删除某个节点，先将此节点移除，然后将最后一个节点暂时安放在删除节点的位置；开始比较最后一个节点和其左右子节点的大小，如果是比两个子节点都小，那么终止下沉操作，生成新的二叉堆，如果是比其中任何一个子节点大，那么就将此节点和其子节点中最小的那个互换位置，依次循环，直到没有子节点或者比子节点小，终止下沉操作，生成最终的新二叉堆。下面请看图解：
- 在原二叉堆 ( 0 1 2 7 3 5 6 10 8 9 ) 中删除其根节点 0，第一步就是将最后节点 9 暂时移到根节点处
- 第二步对比 9 这个节点和其子节点中最小的大小，最小节点为 1，而且 9 比其子节点 1 要大，那么就将其互换位置，得到如下图所示：
- 第三步继续对比此时的 9 节点和其子节点的大小，此时它的子节点中最小的是 3 ，而 9 节点又比 3 要大，那么继续互换位置，如下图：
- 第四步准备继续对比，发现此时的 9 节点没有子节点了，那么就终止对比，生成新的二叉堆 ( 1 3 2 7 9 5 6 10 8 )：
代码实现起来如下：
/**
* 删除一个结点，同时进行下沉操作
*
* @param element 删除的结点
*/
public void deleteNode(Integer element) {
if (_data.isEmpty()) {
return;
}
int index = _data.indexOf(element);
if (index == -1) {
return;
}
if (index == _data.size() - 1) {
_data.remove(_data.size() - 1);
return;
}
int size = _data.size();
_data.set(index, _data.get(size - 1));
_data.remove(size - 1);
if (size > 1) {
down(index, _data.size() - 1);
}
}
/**
* 下沉
*
* @param start 下沉起始坐标
* @param end 下沉终点坐标
*/
private void down(int start, int end) {
int left = start * 2 + 1;
Integer temp = _data.get(start);
while (left <= end) {
boolean max = true;
// 防止index越界
if (left + 1 <= end) {
// 对比左右子节点，如果右子节点比左小，那么left取右子节点的下标
max = (_data.get(left) - _data.get(left + 1)) < 0;
}
if (!max && left <= end) {
left++;
}
// 如果子节点小于父节点，那么交换位置
// 并且继续检查子节点和其子节点的大小关系
max = (temp - _data.get(left)) > 0;
if (!max) break;
else {
_data.set(start, _data.get(left));
start = left;
left = left * 2 + 1;
}
}
_data.set(start, temp);
}
二叉堆在理解二叉树的知识之后，上手理解还是比较轻松的，而且二叉堆的应用很广，比如我们使用的堆排序，就是完美的使用了二叉堆中删除节点的操作，可以试想一下，对于一个最小堆来说，依次删除根节点，拿到顺序不就是从最小值开始的么。而且我们还可以取一个数组或者列表中前K个最小值。所以二叉堆的知识还是有必要熟练掌握的！
下面我把整体代码贴出来，以便大家在熟悉过程中可以跟着代码结果来对比。
import java.util.ArrayList;
import java.util.List;
class BinaryHeap {
private List<Integer> _data;
public BinaryHeap() {
_data = new ArrayList<>();
}
/**
* 添加一个结点
*
* @param element 结点值
*/
public void addNode(Integer element) {
_data.add(element);
up();
}
/**
* 进行上浮操作
*/
private void up() {
int tempIndex = _data.size() - 1;
int parentIndex = (tempIndex - 1) / 2;
Integer temp = _data.get(tempIndex);
while (tempIndex > 0) {
int cmp = _data.get(parentIndex) - temp;
if (cmp <= 0) {
break;
} else {
_data.set(tempIndex, _data.get(parentIndex));
tempIndex = parentIndex;
parentIndex = (parentIndex - 1) / 2;
}
}
_data.set(tempIndex, temp);
}
/**
* 删除一个结点，同时进行下沉操作
*
* @param element 删除的结点
*/
public void deleteNode(Integer element) {
if (_data.isEmpty()) {
return;
}
int index = _data.indexOf(element);
if (index == -1) {
return;
}
if (index == _data.size() - 1) {
_data.remove(_data.size() - 1);
return;
}
int size = _data.size();
_data.set(index, _data.get(size - 1));
_data.remove(size - 1);
if (size > 1) {
down(index, _data.size() - 1);
}
}
/**
* 下沉
*
* @param start 下沉起始坐标
* @param end 下沉终点坐标
*/
private void down(int start, int end) {
int left = start * 2 + 1;
Integer temp = _data.get(start);
while (left <= end) {
boolean max = true;
// 防止index越界
if (left + 1 <= end) {
// 对比左右子节点，如果右子节点比左小，那么left取右子节点的下标
max = (_data.get(left) - _data.get(left + 1)) < 0;
}
if (!max && left <= end) {
left++;
}
// 如果子节点小于父节点，那么交换位置
// 并且继续检查子节点和其子节点的大小关系
max = (temp - _data.get(left)) > 0;
if (!max) break;
else {
_data.set(start, _data.get(left));
start = left;
left = left * 2 + 1;
}
}
_data.set(start, temp);
}
@Override
public String toString() {
StringBuilder result = new StringBuilder();
_data.forEach(element -> result.append(element).append(" "));
return result.toString();
}
public static void main(String[] args) {
Integer[] data = {0, 3, 2, 7, 9, 5, 6, 10, 8};
BinaryHeap binaryHeap = new BinaryHeap();
for (Integer element : data) {
binaryHeap.addNode(element);
}
binaryHeap.addNode(1);
System.out.println(binaryHeap.toString());
binaryHeap.deleteNode(0);
System.out.println(binaryHeap.toString());
}
}
如果本文章你发现有不正确或者不足之处，欢迎你在下方留言或者扫描下方的二维码留言也可！
