详解二叉堆，及优先级队列实现

ゝ一世哀愁。 2022-09-14 13:27 204阅读 0赞

首先介绍下满二叉树和完全二叉树

一、满二叉树，非叶子节点的度为2（有两个子节点），叶子节点全部处于同一层上

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16][]

满二叉树

满二叉树除了满足普通二叉树的性质，还具有以下性质：

1、满二叉树中第 i 层的节点数为![2^\{i-1\}][2_i-1]个。  
2、深度为 k 的满二叉树必有![2^\{k\}-1][2_k_-1]个节点 ，叶子数为![2^\{k-1\}][2_k-1] 。  
3、满二叉树中不存在度为 1 的节点，每一个分支点中都两棵深度相同的子树，且叶子节点都在最底层。  
4、具有 n 个节点的满二叉树的深度为![\{log\_\{2\}\}^\{n+1\}][log_2_n_1]。

二、完全二叉树

如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从**左到右分布**，则此二叉树被称为完全二叉树。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 1][]

三、二叉堆

二叉堆是一种特殊的堆，二叉堆是完全二元树（二叉树）或者是近似完全二元树（二叉树）。二叉堆有两种：**最大堆**和**最小堆**。最大堆：父节点的键值总是大于或等于任何一个子节点的键值；最小堆：父结点的键值总是小于或等于任何一个子节点的键值。二叉堆一般是用数组来存储。那看下如下的完全二叉树是如何存储在数组中的，以及如何定位父节点，子节点

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_18_color_FFFFFF_t_70_g_se_x_16][]

如果 树中节点个数是 x ，则申请一个 x+1（索引为 0 的位置空着不用） 大小的数组，用来存放节点，则可以转换为如下所示

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_17_color_FFFFFF_t_70_g_se_x_16][]  
有如下问题需要处理  
（1）传入一个节点的下标索引，如何找出其 **左** 节点的索引，如我们获取索引（ index = 2）的左节点所存的索引，为 2 \* index

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 2][]

//左孩子的索引
    private int left(int index)
    {
        return 2 * index ;
    }

（2）同理传入一个节点的下标索引，如何找出其 **右** 节点的索引，如我们获取索引（ index = 2）的右节点所存的索引，为 2 \* index + 1；

//右孩子的索引
    private int right(int index)
    {
        return 2 * index + 1;
    }

（3）同理也可以获得父节点的索引

//父节点的索引
    private int parent(int index)
    {
        return  index / 2;
    }

上面说过二叉堆分为最大堆和最小堆：

最大堆：父节点的键值总是大于或等于任何一个子节点的键值
    最小堆：父结点的键值总是小于或等于任何一个子节点的键值

下面以最大堆进行说明，最小堆是一样的道理

对于一个最大堆，根据其性质，显然堆顶，也就是 arr\[1\] 一定是所有元素中最大的元素。

--------------------

**优先级队列**

队列是一种常见的数据结构，一般是在一端进行元素的插入，一端进行元素的取出，按照先入先出的顺序进行数据的处理

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_19_color_FFFFFF_t_70_g_se_x_16][]

但是有时候任务的优先级、重要性等等是不一样的，不能简单的按照进入的顺序来进行处理，需要优先处理优先级高，重要的任务。这个时候我们就需要快速的拿到优先级/重要性比较高的一个任务。优先级队列可以解决这个问题。

优先级队列提供的操作

数据结构的功能操作和功能无非就是增删改查，优先级队列有两个主要 API，分别是push插入一个元素到队列中和`delMax从队列中删除`最大元素（如果底层用最小堆，那么就是`delMin`）

package com.Ycb.queue;
    
    public class MaxPQueue<T extends Comparable<T>> {
        //存储元素的数组
        private T[] pq;
        //当前优先级队列中元素的个数
        private int N;
    
        public MaxPQueue(int capacity) {
            if (capacity <= 0) {
                throw new IllegalArgumentException("队列的容量必须大于0,capacity = " + capacity);
            }
            this.pq = (T[]) new Comparable[capacity + 1];
            this.N = 0;
        }
    
    
        /**
         * 获取队列中最大的元素
         *
         * @return
         */
        public T getMax() {
        }
    
        /**
         * 向队列中入队一个元素
         *
         * @param value
         */
        public void push(T value) {
    
        }
    
        /**
         * 删除队列中最大的元素，并返回最大元素
         *
         * @return
         */
        public T delMax() {
    
        }
    
        /**
         * 上浮第k个位置的元素，以保持最大堆的性质
         *
         * @param k
         */
        private void swim(int k) {
    
        }
    
        /**
         * 下沉第 k 个位置的元素，以保持最大堆的性质
         *
         * @param k
         */
        private void sink(int k) {
    
        }
    
        /**
         * 判断队列是否为空
         *
         * @return
         */
        public boolean isEmpty() {
            return N == 0;
        }
    
        /**
         * 获取队列中的元素个数
         *
         * @return
         */
        public int size() {
            return N;
        }
    
        /**
         * 交换位置x和位置y的元素
         *
         * @param x
         * @param y
         */
        private void exchange(int x, int y) {
            T temp = pq[x];
            pq[x] = pq[y];
            pq[y] = temp;
        }
    
        /**
         * 获取index对应元素的左节点的索引
         *
         * @param index
         * @return
         */
        private int left(int index) {
            return 2 * index;
        }
    
        /**
         * 获取index对应元素的右节点的索引
         *
         * @param index
         * @return
         */
        private int right(int index) {
            return 2 * index + 1;
        }
    
        /**
         * 获取index的父节点的索引
         *
         * @param index
         * @return
         */
        private int parent(int index) {
            return index / 2;
        }
    
        private boolean less(int x, int y) {
            return pq[x].compareTo(pq[y]) < 0;
        }
    }

初步定义了一些比较常用的API，如上代码段所示，此处使用java里面的泛型，可以理解为是可比较大小的任何类型，如Integer，Character等等。其实核心的就是两个方法，分别是swim（上浮）和sink（下沉）。

swim（上浮）方法的实现

为啥需要swim？当往堆里面插入元素时一般都是插入在堆的尾部，此时有可能会破坏堆的性质，所以我们需要为新插入的元素找到合适的位置，此时就需要上浮以维护堆的性质，如下所示，有三个元素组成的堆。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_17_color_FFFFFF_t_70_g_se_x_16 1][]

当我们再往堆中插入一个元素，如元素4，此时的情况如下图所示。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_17_color_FFFFFF_t_70_g_se_x_16 2][]

我们可以发现元素 1 的孩子不满足所有子节点都比自身小，破坏了堆的性质，所以需要把新插入的元素 4 往上swim（上浮）以便找到合适的位置，从而保证堆的性质不被破坏。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 3][]

上浮一次之后，发现还是不满足堆的性质，所以还得继续上浮，直到堆顶为止（即直到走到树的根部，跟之后就没有父节点了）。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 4][]

经分析，swim的代码如下：

/**
         * 上浮第k个位置的元素，以保持最大堆的性质
         *
         * @param k
         */
        private void swim(int k) {
            // k>1 表示一直向上浮动，直到跟节点
            while (k > 1 && less(parent(k), k)) {
                //交换父子节点的值，更大的元素往上浮动一次
                exchange(parent(k), k);
    
                //上浮一次之后需要上浮的位置也需要跟着变
                k = parent(k);
            }
        }

sink（下沉）方法的实现

如下所示的堆，此时如果我们移除最大元素，一般都是把最后的元素置于堆顶

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_16_color_FFFFFF_t_70_g_se_x_16][]

移除最大元素，同时最后一个元素放置到堆顶后如下图所示。此处我把这个最大的元素移动到堆底，也就是与最后一个元素进行交换，其实这也是堆排序的时候用到的，但是后续堆化都不能考虑这个元素了，即后续 元素 5 不参与堆化了，当然我这里实现优先级队列，直接移除的，此处方便展示还是把这个元素 5 体现在树中。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 5][]

通过上图，可以看出，当移除元素 5 时，元素 1 移动到堆顶，此时堆的性质被破坏，因为元素 1 并不比两个子节点 4 和 2 大，所以需要把元素 1 下沉到合适的（满足堆性质）位置。如下图所示，移除最大元素 5 ，同时把元素 1 移动到堆顶时如下图所示，显然不满足大顶堆的性质，所以元素 1 需要下沉，以满足 大顶堆的性质。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_12_color_FFFFFF_t_70_g_se_x_16][]

sink（下沉）比swim（上浮）稍微复杂一点，需要考虑以下问题

1、什么时机该终止下沉
    2、左节点是否存在
    3、右节点是否存在
    4、与左节点交换还是与右节点交换

**问题1**、什么时机该终止下沉？  
（1）当没有子节点时，说明已经到叶子节点，不再需要执行下沉操作  
（2）当节点的值比两个子节点都大时，说明节点已经找到合理（满足大顶堆特性）的位置，也不 再需要执行下沉操作

**问题2**、左节点是否存在？  
计算出左节点的索引，看是否越界

**问题3**、右节点是否存在？  
如果左节点存在，才会去判断右节点是否存在，对于右节点的存在与否，也可以先计算出右节点的索引，然后判断索引是否越界，如果不越界说明存在。

**问题4**、与左节点交换还是与右节点交换  
（1）当只存在左节点时自然只需要与左节点进行比较和交换  
（2）当存在左右节点时，需要与左右节点中大的节点进行交换

下面以如下堆进行说明

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 5][]

移除 5 之后，1 移动到堆顶，因为破坏了堆的性质，所以需要把元素 1 进行下沉以满足大顶堆的性质。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 6][]

元素 1（k = 1） 的 左节点（left = 2） 和 右节点（right = 3） 都是存在的，所以需要与大的一个元素（maxIndex）进行交换，同时设置 k = maxIndex

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 7][]

如上图所示，因为pq\[leftIndex\] > pq\[rightIndex\] ，所以执行exchange(k,leftIndex)，同时设置 k = leftIndex。再继续执行后续操作。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 8][]

经过上面几步，经过元素的不断下沉，元素都在合适的位置，已经满足了大顶堆的性质，代码如下

/**
         * 下沉第 k 个位置的元素，以保持最大堆的性质
         *
         * @param k
         */
        private void sink(int k) {
            //左节点都不存在，说明是叶子节点
            while (left(k) <= N) {
                //左节点已经存在，所以假设左节点是最大的值
                int maxIndex = left(k);
    
                //如果右节点存在，则对比一下大小，选择大的一个节点
                if (right(k) <= N && less(maxIndex, right(k))) {
                    maxIndex = right(k);
                }
    
                //如果maxIndex已经比k所在的元素下，则不需要再进行比较
                if (less(maxIndex, k)) break;
    
                //交换maxIndex 和 k 的元素
                exchange(maxIndex, k);
    
                //同时设置k = maxIndex，继续往下沉
                k = maxIndex;
            }
        }

经过上面分析，swim（上浮）和sink（下沉）的相关逻辑都已经实现，结合图和代码比较好理解，接下来看下其他的方法

getMax

getMax比较简单，直接获取堆顶元素就可以（当然需要判断堆是否为空，如果是空，抛出异常或者是返回null都可以），否则返回堆顶元素

/**
         * 获取队列中最大的元素
         *
         * @return 如果堆为空，返回null,否则返回堆顶元素
         */
        public T getMax() {
            if (isEmpty()) return null;
            return pq[1];
        }

push push大概经过以下几步

1、push之前应该先判断队列是否已满，如果队列满了，可以进行相应的操作
       （1）扩容，留到后面实现了
       （2）抛出异常，此处选择这一种。
    2、队列中的元素 + 1
    3、元素进入队列，进入队列尾部
    4、把刚刚加入的元素swim（上浮），以保证大顶堆的合理性

初始 有 如下堆

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_19_color_FFFFFF_t_70_g_se_x_16 1][]

现在往堆中加入元素 4

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_19_color_FFFFFF_t_70_g_se_x_16 2][]

需要把元素4进行上浮，把元素 4 放置到合理的位置，以保证大顶堆的性质不被破坏

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 9][]

代码如下：

/**
         * 向队列中入队一个元素
         *
         * @param value
         */
        public void push(T value) throws Exception {
            if (N == pq.length - 1) {
                throw new Exception("队列已满！");
            }
            //队列中元素+1；
            N++;
            //元素进入队列
            pq[N] = value;
            //上浮
            swim(N);
        }

delMax delMax大概经过如下几个步骤

1、如果队列为空，返回空或者抛出异常，此处以返回null|
    2、取出最大元素，存放，方便后续返回
    3、交换第一个和第N个元素
    4、队列中的第N个元素置为空
    5、N--
    6、pq[1] sink（下沉）到合理的位置

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 10][]

代码如下：

/**
         * 删除队列中最大的元素，并返回最大元素
         *
         * @return
         */
        public T delMax() {
            if (isEmpty()) return null;
            //取出
            T max = pq[1];
            //交换
            exchange(1, N);
            //置为空
            pq[N] = null;
            //元素-1
            N--;
            //下沉 k = 1
            sink(1);
            return max;
        }

其实只要理解了优先级队列的实现，主要是sink和swim的实现，堆排序就很简单了，后续有时间再完善了。

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/31066dbd23b146af88d145e85c851ac5.png
[2_i-1]: https://latex.codecogs.com/gif.latex?2%5E%7Bi-1%7D
[2_k_-1]: https://latex.codecogs.com/gif.latex?2%5E%7Bk%7D-1
[2_k-1]: https://latex.codecogs.com/gif.latex?2%5E%7Bk-1%7D
[log_2_n_1]: https://latex.codecogs.com/gif.latex?%7Blog_%7B2%7D%7D%5E%7Bn&plus;1%7D
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/ab69f4b7c6874ce093a95bc6845888ad.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_18_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/5e0326b8752d4676b5aa90ac5da16509.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_17_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/3f6729d6b5e74881bf4901b2b54e7ea9.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/8e5d39772e974eb9a52c2412d9186e88.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_19_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/c7b9573fac974495baf52e9da9c4e74b.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_17_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/71b5dedb16e2454fa2612b820dd1a7de.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_17_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/7e38c33738f843719c9165e57eb63788.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/1b96790015024900af4acb4b58aca9ab.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/0b9444e04be74743b35e15d0a250419c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_16_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/9589e27e9b144b40838fb931d6edc216.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220828/68e1e9ca455c44bd8fb9890a95224242.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_12_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/b422b6b223d14503b800a583478265d6.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220828/f1336cd9a1af4b52aa8032cc8be3676c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 7]: /images/20220828/7624ad6c44ac45da8aa33182ae0b6697.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 8]: /images/20220828/4c426fe634394cf1bda909841b6486ee.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_19_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/8777c58b919a42659b01eb1af8ff8448.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_19_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/4e5f26a23a484a0d854b37744ab007de.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 9]: /images/20220828/3bc8b720b98249b3af6080c7fee3628c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 10]: /images/20220828/bb26b18e27a04ceca0474bab3f32a583.png