Home未分类隐藏在优先级队列后边的那个神秘结构

隐藏在优先级队列后边的那个神秘结构

2009 年 8 月 18 日




小贴士：






本文中的图使用PS画的，真可谓杀鸡用牛刀～


PriorityQueue
翻译成中文就是
优先级队列
。所谓
优先级队列
，就意味着一个优先级比较高的元素
入队
的话，可能并不是直接插到队尾，可以根据他的优先级等级插入到队中的某个地方，如果他的优先级特别特别高，就会直接被插入到
队首
。举个栗子可能更好理解，比如火车站排队的时候是军人优先的，如果一个兵哥哥来排队的话，他可以直接插到队首去买票，而不是像普通旅客一样从最后排起。

小贴士：当然现实中兵哥哥一般也不会用这种特权～

下边我们给个例子来看一下这个所谓的
优先级队列
怎么使用：

public class Test {

public static void main(String[] args) {
        Queue queue = new PriorityQueue();
        queue.add(5);    //第1步
        queue.add(7);    //第2步
        queue.add(3);    //第3步
        queue.add(4);    //第4步
        queue.add(2);    //第5步
        queue.add(9);    //第6步
        queue.add(1);    //第7步

        Integer i = queue.poll();   //获取并移除一个元素
while (i != null) {
            System.out.println(i);
            i = queue.poll();
        }
    }
}

我们看一下输出结果：

从输出结果中我们可以看出来，虽然入队时的数字大小是随机的，但是出队时的数字大小是有序的，这是怎么做到的呢？因为引入了一种称之为
二叉堆
的东东。


二叉堆

其实，
PriorityQueue
内部使用了
数组
来实际存储数据，我们前边也说过，
ArrayList
内部也是用数组来存储数据的，让我们来对比一下这两个底层都用
数组
来存储元素的容器的元素添加过程。

先来看一下用
ArrayList
的方式来添加元素的过程：

List list = new ArrayList();
list.add(5);    //第1步
list.add(7);    //第2步
list.add(3);    //第3步
list.add(4);    //第4步
list.add(2);    //第5步
list.add(9);    //第6步
list.add(1);    //第7步

我们分步骤来看一下添加过程：

可以看到，
ArrayList
插入元素的方式很简单，直接往后怼就对了～

我们再看一下
PriorityQueue
容器的元素添加过程：

Queue queue = new PriorityQueue();
queue.add(5);    //第1步
queue.add(7);    //第2步
queue.add(3);    //第3步
queue.add(4);    //第4步
queue.add(2);    //第5步
queue.add(9);    //第6步
queue.add(1);    //第7步

在分析添加步骤之前，我们先看下添加完这些元素之后，内部的数组长什么样：

大家从结果图中可以看出来，我们的插入顺序是：
5、7、3、4、2、9、1
，而真正的数组顺序是
1、3、2、7、4、9、5
，
add
方法肯定是搞了什么猫腻～ 其实之所以是
1、3、2、7、4、9、5
这样的数字序列，是因为这个数字序列就是下边这种抽象的逻辑结构的一个从上到下，从左到右的一个数字序列：

先看看这种抽象的逻辑结构有什么特点：

  1. 每一个圆圈代表一个
    节点
    ，值为
    1
    的节点被称之为
    根节点
    。

  2. 除
    根节点
    外，每一个节点都有一个
    父节点
    ，比如说值为
    1
    的节点是值为
    3
    的节点的父节点，值为
    9
    的节点的父节点是值为
    2
    的节点。

  3. 一个节点最多有两个子节点，比如值为
    1
    的节点的子节点就是值为
    3
    和
    2
    的两个节点。我们可以称在左边的子节点为
    左孩子
    ，在右边的子节点为
    右孩子
    。

  4. 在填充元素的时候，按照从上往下，从左往右的顺序依次填充，中间不能跳过某些节点。

    比方说下边这两个栗子就不是
    二叉堆
    ：

  5. 二叉堆
    分两种，第一种是
    大顶堆
    ，就是父节点的值大于它的子节点的值。第二种是
    小顶堆
    ，就是父节点的值小于它的子节点的值。我们上边的栗子中的
    二叉堆
    就是
    小顶堆
    。


我们把这种 抽象的逻辑结构
称为
二叉堆

。 它的提出只是为了我们人类方便的解决问题
。它具有一个非常好的性质，那就是：

对于 小顶堆
来说，根节点永远都是最小的节点
。这样就非常利于我们优先级队列的实现喽。

我们一再强调
二叉堆

是一种 抽象的逻辑结构
，也就是说这只是给人来分析问题用的，至于这个逻辑结构具体使用链表还是数组去实际实现是另一回事儿。不过
PriorityQueue
采用了数组来实际存储这种结构的数据，我们马上来看数组是怎么实现这种逻辑结构的。


堆与数组的映射

按照从上到下，从左到右的顺序依次把
二叉堆
里边的元素填入数组中，比方说下边这个
二叉堆
结构：

根节点的元素就对应数组的0号下标的元素，值为
3
的节点就对应1号下标，值为
6
的节点就对应2号下标，以此类推。

有一点很重要，我们可以用数组的下标来确定父节点和孩子节点的相对关系，下标计算如下：

下标为i的节点的左孩子的下标：Left(i) = 2 * i + 1
下标为i的节点的右孩子的下标：Right(i) = 2 * i + 2
下标为i的节点的父节点的下标：Parent(i) = (i-1)/2

拿上图举例，比方说下标为1的节点，它的值是
3
：

左孩子的下标：Left(1) = 2 * 1 + 1 = 3。右孩子的下标：Right(1) = 2 * 1 + 2 = 4。父节点的下标：Parent(1) = (1 – 1)/ 2 = 0。

PriorityQueue
内使用的是
小顶堆
的结构，所以为了维持
二叉堆
的特点，每向堆内插入一个元素的时候，都要维持好父节点的值大与两个子节点的值，所以需要遵循这样的插入算法：

  1. 如果插入的节点值大于或等于它父节点的值，则插入成功。
  2. 如果插入的节点值小于它父节点的值，则需要把刚插入的这个节点和它父节点做交换。交换后继续和它上层的父节点做比较，重复这个规则。

现在回到上边的例子，我们将顺序为
5、7、3、4、2、9、1
的元素依次插入
PriorityQueue
优先级队列，画图分析一下这个过程：

为了维持
小顶堆
的特性，上图展示了插入元素时每一步的做的节点交换，橙黄色的节点表示需要交换。

看完了每一步的插入元素示意图之后，我们就知道了
PriorityQueue
中的内部数组的元素排列为什么不是插入时的顺序，而是
1、3、2、7、4、9、5
这样的数字序列了～有了这个
二叉堆
，大家知道为什么我们每次获取队头的时候都是返回最小的那个元素了吧，就是直接把二叉堆的根元素给拿出来了哈哈～

我们这里只是重点唠叨了它的实现原理，具体的代码就不写了，大家有空一定要自己把这个
PriorityQueue
去实现一遍，如果不会写的话查看一下源代码哈～

小青蛙历史文章：

长按关注小青蛙，都是干货喔

Related Posts

About The Author

fenny