图解二叉堆

>>2020,微服务装逼指南

二叉堆本质上其实就是一种完全二叉树(不熟悉二叉树的可以看前面的文章:图解二叉树,它分为两种类型:

  • 最大堆:堆中任何一个父节点的值都大于等于它左右子节点的值

    图解二叉堆
  • 最小堆:显然和最大堆相反,堆中任何一个父节点的值都小于等于它左右子节点的值

    图解二叉堆

对于一个二叉堆的操作主要包含了两个:插入节点和删除节点;接下来会对这两种操作进行具体的说明,说明的对象都是最小堆,如果理解了最小堆的操作,那么最大堆的操作就易如反掌了。

插入节点 (最小堆)

插入一个节点主要的逻辑就是在二叉树的最后节点上安置新的节点,然后比较此节点和父节点的大小。如果是小于父节点,那么就不用操作,直接生成此二叉堆;如果是大于父节点,那么将此节点和父节点位置互换(也就是上浮操作),将互换后的父节点作为新的节点,再进行新节点和父节点的大小比较,直到新节点小于父节点或者新节点为根节点,结束。文字的表现力依旧比较复杂,下面就看插入的流程图吧,结合流程图会更加贴切的理解插入过程。

  1. 在现有的二叉堆 ( 0, 3, 2, 7, 9, 5, 6, 10, 8 ) 中插入新的节点 1

    图解二叉堆
  2. 新节点与父节点对比,新节点 1 小于 父节点 9,那么就互换位置

    图解二叉堆
  3. 互换后的节点 1 再与其父节点对比,1 小于其父节点 3,再次互换位置

    图解二叉堆
  4. 再看此时的新节点 1,对于其现有父节点 0,它是大于其父节点的,所以终止上浮操作,生成最终的二叉堆 ( 0 1 2 7 3 5 6 10 8 9 ),如上图所示。
    下面看具体的代码实现:

 1    /**
2     * 添加一个结点
3     *
4     * @param element 结点值
5     */

6    public void addNode(Integer element) {
7        _data.add(element);
8        up();
9    }
10
11    /**
12     * 进行上浮操作
13     */

14    private void up() {
15        int tempIndex = _data.size() - 1;
16        int parentIndex = (tempIndex - 1) / 2;
17        Integer temp = _data.get(tempIndex);
18
19        while (tempIndex > 0) {
20            int cmp = _data.get(parentIndex) - temp;
21            if (cmp <= 0) {
22                break;
23            } else {
24                _data.set(tempIndex, _data.get(parentIndex));
25                tempIndex = parentIndex;
26                parentIndex = (parentIndex - 1) / 2;
27            }
28        }
29        _data.set(tempIndex, temp);
30    }

删除节点 (最小堆)

删除节点的操作和逻辑要比添加节点稍微复杂那么一丢丢,但是其本质还是一样的,比较子节点和父节点的大小进行下沉操作。删除某个节点,先将此节点移除,然后将最后一个节点暂时安放在删除节点的位置;开始比较最后一个节点和其左右子节点的大小,如果是比两个子节点都小,那么终止下沉操作,生成新的二叉堆,如果是比其中任何一个子节点大,那么就将此节点和其子节点中最小的那个互换位置,依次循环,直到没有子节点或者比子节点小,终止下沉操作,生成最终的新二叉堆。下面请看图解:

  1. 在原二叉堆 ( 0 1 2 7 3 5 6 10 8 9 ) 中删除其根节点 0,第一步就是将最后节点 9 暂时移到根节点处

    图解二叉堆
  2. 第二步对比 9 这个节点和其子节点中最小的大小,最小节点为 1,而且 9 比其子节点 1 要大,那么就将其互换位置,得到如下图所示:

    图解二叉堆
  3. 第三步继续对比此时的 9 节点和其子节点的大小,此时它的子节点中最小的是 3 ,而 9 节点又比 3 要大,那么继续互换位置,如下图:

    图解二叉堆
  4. 第四步准备继续对比,发现此时的 9 节点没有子节点了,那么就终止对比,生成新的二叉堆 ( 1 3 2 7 9 5 6 10 8 ):

    图解二叉堆

    代码实现起来如下:

 1/**
2     * 删除一个结点,同时进行下沉操作
3     *
4     * @param element 删除的结点
5     */

6    public void deleteNode(Integer element) {
7        if (_data.isEmpty()) {
8            return;
9        }
10        int index = _data.indexOf(element);
11        if (index == -1) {
12            return;
13        }
14        if (index == _data.size() - 1) {
15            _data.remove(_data.size() - 1);
16            return;
17        }
18        int size = _data.size();
19        _data.set(index, _data.get(size - 1));
20        _data.remove(size - 1);
21        if (size > 1) {
22            down(index, _data.size() - 1);
23        }
24    }
25
26    /**
27     * 下沉
28     *
29     * @param start 下沉起始坐标
30     * @param end   下沉终点坐标
31     */

32    private void down(int start, int end) {
33        int left = start * 2 + 1;
34        Integer temp = _data.get(start);
35        while (left <= end) {
36            boolean max = true;
37            // 防止index越界
38            if (left + 1 <= end) {
39                // 对比左右子节点,如果右子节点比左小,那么left取右子节点的下标
40                max = (_data.get(left) - _data.get(left + 1)) < 0;
41            }
42            if (!max && left <= end) {
43                left++;
44            }
45            // 如果子节点小于父节点,那么交换位置
46            // 并且继续检查子节点和其子节点的大小关系
47            max = (temp - _data.get(left)) > 0;
48            if (!max) break;
49            else {
50                _data.set(start, _data.get(left));
51                start = left;
52                left = left * 2 + 1;
53            }
54        }
55        _data.set(start, temp);
56    }

二叉堆在理解二叉树的知识之后,上手理解还是比较轻松的,而且二叉堆的应用很广,比如我们使用的堆排序,就是完美的使用了二叉堆中删除节点的操作,可以试想一下,对于一个最小堆来说,依次删除根节点,拿到顺序不就是从最小值开始的么。而且我们还可以取一个数组或者列表中前K个最小值。所以二叉堆的知识还是有必要熟练掌握的!
下面我把整体代码贴出来,以便大家在熟悉过程中可以跟着代码结果来对比。

  1import java.util.ArrayList;
2import java.util.List;
3
4class BinaryHeap {
5
6    private List<Integer> _data;
7
8    public BinaryHeap() {
9        _data = new ArrayList<>();
10    }
11
12    /**
13     * 添加一个结点
14     *
15     * @param element 结点值
16     */

17    public void addNode(Integer element) {
18        _data.add(element);
19        up();
20    }
21
22    /**
23     * 进行上浮操作
24     */

25    private void up() {
26        int tempIndex = _data.size() - 1;
27        int parentIndex = (tempIndex - 1) / 2;
28        Integer temp = _data.get(tempIndex);
29
30        while (tempIndex > 0) {
31            int cmp = _data.get(parentIndex) - temp;
32            if (cmp <= 0) {
33                break;
34            } else {
35                _data.set(tempIndex, _data.get(parentIndex));
36                tempIndex = parentIndex;
37                parentIndex = (parentIndex - 1) / 2;
38            }
39        }
40        _data.set(tempIndex, temp);
41    }
42
43    /**
44     * 删除一个结点,同时进行下沉操作
45     *
46     * @param element 删除的结点
47     */

48    public void deleteNode(Integer element) {
49        if (_data.isEmpty()) {
50            return;
51        }
52        int index = _data.indexOf(element);
53        if (index == -1) {
54            return;
55        }
56        if (index == _data.size() - 1) {
57            _data.remove(_data.size() - 1);
58            return;
59        }
60        int size = _data.size();
61        _data.set(index, _data.get(size - 1));
62        _data.remove(size - 1);
63        if (size > 1) {
64            down(index, _data.size() - 1);
65        }
66    }
67
68    /**
69     * 下沉
70     *
71     * @param start 下沉起始坐标
72     * @param end   下沉终点坐标
73     */

74    private void down(int start, int end) {
75        int left = start * 2 + 1;
76        Integer temp = _data.get(start);
77        while (left <= end) {
78            boolean max = true;
79            // 防止index越界
80            if (left + 1 <= end) {
81                // 对比左右子节点,如果右子节点比左小,那么left取右子节点的下标
82                max = (_data.get(left) - _data.get(left + 1)) < 0;
83            }
84            if (!max && left <= end) {
85                left++;
86            }
87            // 如果子节点小于父节点,那么交换位置
88            // 并且继续检查子节点和其子节点的大小关系
89            max = (temp - _data.get(left)) > 0;
90            if (!max) break;
91            else {
92                _data.set(start, _data.get(left));
93                start = left;
94                left = left * 2 + 1;
95            }
96        }
97        _data.set(start, temp);
98    }
99
100    @Override
101    public String toString() {
102        StringBuilder result = new StringBuilder();
103        _data.forEach(element -> result.append(element).append(" "));
104        return result.toString();
105    }
106
107    public static void main(String[] args) {
108        Integer[] data = {0327956108};
109        BinaryHeap binaryHeap = new BinaryHeap();
110        for (Integer element : data) {
111            binaryHeap.addNode(element);
112        }
113        binaryHeap.addNode(1);
114        System.out.println(binaryHeap.toString());
115        binaryHeap.deleteNode(0);
116        System.out.println(binaryHeap.toString());
117    }
118}

如果本文章你发现有不正确或者不足之处,欢迎你在下方留言或者扫描下方的二维码留言也可!

图解二叉堆


原文始发于微信公众号(Taonce):图解二叉堆