堆(heap)又被为优先队列(priority queue)。尽管名为优先队列,但堆并不是队列。

因为队列中允许的操作是先进先出(FIFO),在队尾插入元素,在队头取出元素。

而堆虽然在堆底插入元素,在堆顶取出元素,但是堆中元素的排列不是按照到来的先后顺序,而是按照一定的优先顺序排列的。

本文通过堆的实现、最小堆(最大堆)、堆的时间复杂度、优先队列的实现、堆排序来介绍「 堆 」。

堆的实现

堆的一个经典的实现是完全二叉树(complete binary tree),这样实现的堆称为二叉堆(binary heap)。

这里来说明一下满二叉树的概念与完全二叉树的概念。

满二叉树:除了叶子节点,所有的节点的左右孩子都不为空,就是一棵满二叉树,如下图。
看动画轻松理解「 堆 」


可以看出:满二叉树所有的节点都拥有左孩子,又拥有右孩子。

完全二叉树:不一定是一个满二叉树,但它不满的那部分一定在右下侧,如下图

看动画轻松理解「 堆 」

堆的特性:

  • 必须是完全二叉树

  • 任一结点的值是其子树所有结点的最大值或最小值

  • 最大值时,称为“最大堆”,也称大顶堆;

  • 最小值时,称为“最小堆”,也称小顶堆。

看动画轻松理解「 堆 」
堆的基础实现

只要谨记堆的定义特性,实现起来其实是很容易的。

  • 特性1.  维持完全二叉树  

  • 特性2.  子类数字总是大于父类数字  

 1public class MinHeap <E extends Comparable<E>> {
2    private Array<E> data;
3
4    public MinHeap(int capacity){
5        data = new Array<>(capacity);
6    }
7
8    public MinHeap(){
9        data = new Array<>();
10    }
11
12    // 返回堆中的元素个数
13    public int size(){
14        return data.getSize();
15    }
16
17    // 返回一个布尔值, 表示堆中是否为空
18    public boolean isEmpty(){
19        return data.isEmpty();
20    }
21
22    // 返回完全二叉树的数组表示中,一个索引所表示的元素的父亲节点的索引
23    private int parent(int index){
24        return (index - 1) / 2;
25    }
26
27    // 返回完全二叉树的数组表示中,一个索引所表示的元素的左孩子节点的索引
28    private int leftChild(int index){
29        return index * 2 + 1;
30    }
31
32    // 返回完全二叉树的数组表示中,一个索引所表示的元素的右孩子节点的索引
33    private int rightChild(int index){
34        return index * 2 + 2;
35    }
36}

最小堆的插入(ADD)

看动画轻松理解「 堆 」

假设现有元素 5 需要插入,为了维持完全二叉树的特性,新插入的元素一定是放在结点 6 的右子树;同时为了满足任一结点的值要小于左右子树的值这一特性,新插入的元素要和其父结点作比较,如果比父结点小,就要把父结点拉下来顶替当前结点的位置,自己则依次不断向上寻找,找到比自己大的父结点就拉下来,直到没有符合条件的值为止。

动画讲解:

  1. 在这里先将元素 5 插入到末尾,即放在结点 6 的右子树。

  2. 然后与父类比较, 6 > 5 ,父类数字大于子类数字,子类与父类交换。

  3. 重复此操作,直到不发生替换。

Show me the code:

添加一个辅助函数,用来交换传入的索引两个位置的元素值

 1/**
2     * 交换传入的索引两个位置的元素值
3     *
4     * @param i
5     * @param j
6     */

7    public void swap(int i, int j) {
8        if (i < 0 || i >= size || j < 0 || j >= size)
9            throw new IllegalArgumentException("Index is illegal.");
10
11        E temp = data[i];
12        data[i] = data[j];
13        data[j] = temp;
14    }

数组中添加交换两元素位置的方法,注意下面代码中注释的描述特性位置。

 1    /**
2     * 堆中添加元素方法。
3     *
4     * @param e
5     */

6    public void add(E e{
7        //特性1:新插入的元素首先放在数组最后,保持完全二叉树的特性
8        data.addLast(e);
9        siftUp(data.getSize() - 1);
10    }
11
12    /**
13     * index 为i位置元素上浮。
14     *
15     * @param i
16     */

17    private void siftUp(int i{
18         //特性2:比较插入值和其父结点的大小关系,小于父结点则用父结点替换当前值,index位置上升为父结点
19        // 当上浮元素大于父亲,继续上浮。并且不能上浮到0之上
20        // 直到i 等于 0 或 比 父亲节点小了。
21        while (i > 0 && data.get(i).compareTo(data.get(parent(i))) > 0) {
22            // 数组Array中添加方法swap
23            data.swap(i, parent(i));
24            i = parent(i); // 这句话让i来到新的位置,使得循环可以查看新的位置是否还要大。
25        }
26    }

最小堆的删除(DELETE)

看动画轻松理解「 堆 」

核心点:将最后一个元素填充到堆顶,然后不断的下沉这个元素。

假设要从节点 1 ,也可以称为取出节点 1 ,为了维持完全二叉树的特性 ,我们将最后一个元素 6 去替代这个 1 ;然后比较 1 和其子树的大小关系,如果比左右子树大(如果存在的话),就要从左右子树中找一个较小的值替换它,而它能自己就要跑到对应子树的位置,再次循环这种操作,直到没有子树比它小。

通过这样的操作,堆依然是堆,总结一下:

  • 找到要删除的节点(取出的节点)在数组中的位置

  • 用数组中最后一个元素替代这个位置的元素

  • 当前位置和其左右子树比较,保证符合最小堆的节点间规则

  • 删除最后一个元素

Show me the code:

 1    public E findMin() {
2        return data.get(0);
3    }
4
5    public E extractMin() {
6
7        E ret = findMin();
8
9        data.swap(0data.getSize() - 1); // 0位置元素和最后一个元素互换。
10        data.removeLast(); // 删除此时的最后一个元素(最小值)
11        siftDown(0); // 对于0处进行siftDown操作
12
13        return ret;
14    }
15
16    /**
17     * k位置元素下移
18     *
19     * @param k
20     */

21    private void siftDown(int k) {
22
23         while(leftChild(k) < data.getSize()){
24            int j = leftChild(k); // 在此轮循环中,data[k]和data[j]交换位置
25            if( j + 1 < data.getSize() &&
26                    data.get(j + 1).compareTo(data.get(j)) < 0 )
27                j ++;
28            // data[j] 是 leftChild 和 rightChild 中的最小值
29
30            if(data.get(k).compareTo(data.get(j)) >= 0 )
31                break;
32
33            data.swap(k, j);
34            k = j;
35        }
36    }

时间复杂度

对于有 n 个节点的堆来说,其高度 d = log2n + 1。 根为第 0 层,则第 i 层结点个数为 2i,
考虑一个元素在堆中向下移动的距离。

  • 大约一半的结点深度为 d-1 ,不移动(叶)。

  • 四分之一的结点深度为 d-2 ,而它们至多能向下移动一层。

  • 树中每向上一层,结点的数目为前一层的一半,而子树高度加一

堆有logn层深,所以插入删除的平均时间和最差时间都是O(logN)

优先队列(priority_queue)

普通队列是一种先进先出的数据结构,先放进队列的元素取值时优先被取出来。而优先队列是一种具有最高优先级元素先出的数据结构,比如每次取值都取最大的元素。

优先队列支持下面的操作:

  • a. 找出优先级最高的元素(最大或最小元素);

  • b. 删除一个具有最高优先级的元素;

  • c. 添加一个元素到集合中。

代码实现

 1public class PriorityQueue<E extends Comparable<E>> implements Queue<E{
2
3    private MaxHeap<E> maxHeap;
4
5    public PriorityQueue(){
6        maxHeap = new MaxHeap<>();
7    }
8
9    @Override
10    public int getSize(){
11        return maxHeap.size();
12    }
13
14    @Override
15    public boolean isEmpty(){
16        return maxHeap.isEmpty();
17    }
18
19    @Override
20    public E getFront(){
21        return maxHeap.findMax();
22    }
23
24    @Override
25    public void enqueue(E e){
26        maxHeap.add(e);
27    }
28
29    @Override
30    public E dequeue(){
31        return maxHeap.extractMax();
32    }
33}

堆排序

理解了优先队列,堆排序的逻辑十分简单。

第一步:让数组形成堆有序状态;

第二步:把堆顶的元素放到数组最末尾,末尾的放到堆顶,在剩下的元素中下沉到正确位置,重复操作即可。

看动画轻松理解「 堆 」
堆排序动画

堆排序详解:【图解数据结构】一组动画彻底理解堆排序

End

关于本号

作者程序员小吴,哈工大学渣,目前正在学算法,开源项目  LeetCodeAnimation 」5100star,GitHub Trending 榜 连续半个月登顶欢迎大家关注我的微信公众号:五分钟学算法,一起学习,一起进步!

看动画轻松理解「 堆 」