Java数据结构第十七期：探索优先级队列的魅力(一)

专栏：Java数据结构秘籍

个人主页：手握风云

目录

一、优先级队列

1.1. 概念

二、优先级队列的模拟实现

2.1. 堆的概念

2.2. 堆的性质

2.3. 堆的存储方式

2.4. 堆的创建

2.5. 堆的插入与删除

2.5.1. 堆的插入

2.5.2. 堆的删除

一、优先级队列

1.1. 概念

        队列是⼀种先进先出(FIFO)的数据结构，但有些情况下，操作的数据可能带有优先 级，⼀般出队列时，可能需要优先级⾼的元素先出队列，在某些场景下，比如在手机上玩游戏时，有人打电话，系统就会优先处理打过来的电话。

        在这种情况下，数据结构应该提供两个最基本的操作，⼀个是返回最⾼优先级对象，⼀个是添加新的对象。这种数据结构就是优先级队列。

二、优先级队列的模拟实现

        优先级队列底层使用了堆这种数据结构，⽽堆实际就是在完全⼆叉树的基础上进⾏了 ⼀些调整。

2.1. 堆的概念

        一个集合K里面的元素按完全⼆叉树的顺序存储⽅式存储在⼀个⼀维数组中，Ki = K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为⼩堆(或⼤堆)。将根节点最⼤的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或 小根堆。

2.2. 堆的性质

• 堆中某个节点的值总是不⼤于或不⼩于其⽗节点的值；
• 堆总是⼀棵完全⼆叉树。

2.3. 堆的存储方式

        堆是⼀棵完全⼆叉树，因此可以层序的规则采⽤顺序的⽅式来⾼效存储。注意：对于⾮完全⼆叉树，则不适合使⽤顺序⽅式进⾏存储，因为为了能够还原⼆叉树，空间中必须要存储空节点，就会导致空间利⽤率⽐较低。

        已知父亲结点下标为i，则左孩子结点为，右孩子结点为。已知孩子结点下标为i，则父亲结点下标为。

2.4. 堆的创建

        前期的准备工作：

public class Heap {
    //储存数据
    public int[] elem;
    //存放有效数据的个数
    public int usedSize;

    public Heap() {
        elem = new int[10];
    }

    //数组初始化
    public void Initial(int[] array){
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            usedSize++;
        }
    }

    //堆的创建
    public void CreateHeap(){

    }
}

public class Test {
    public static void main(String[] args) {
        int[] array = {27,15,19,18,28,34,65,49,25,37};
        Heap newHeap = new Heap();
        newHeap.CreateHeap();
    }
}

        我们接下来通过向下调整来创建我们的大根堆：从每棵子树开始，如果孩子结点的值域比父亲结点的值域大，就交换来实现向下调整。

    //创建堆
    public void CreateHeap() {
        for (int parent = (usedSize - 1 - 1) / 2; parent >= 0; parent--) {
            shiftdown(parent, usedSize);
        }
    }

    private void shiftdown(int parent, int usedSize) {
        int child = 2 * parent + 1;
    }

        我们还得直到每棵子树的调整结束位置。当p传到最后一层时，c往下传就会发生越界，当c的下标等于10（因为数组的下标不可能等于10）时，就代表向下调整已经结束。所以shiftdown方法我们传parent和usedSize两个参数。

        当我们进行向下调整的时候，就是左结点，但有可能这个左结点是不存在的，所以我们需要判断这个下标是否是合法的，并且不能只判断一次，因为c会随着p的值发生变化。

    private void shiftdown(int parent, int usedSize) {
        int child = 2 * parent + 1;
        while (child < usedSize) {
            if (elem[child] < elem[child + 1]) {
                child++;
            }
            //走到这里，child下标一定是左右孩子最大值的下标
            if (elem[child] > elem[parent]) {
                //交换
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                parent = child;
                child = 2 * parent + 1;
            } else {

            }
        }
    }

        代码写到这里，会存在一些问题：如果child等于9，child+1等于10就会越界。所以我们在孩子结点比较之前加上child+1<usedSize。else这句语句，我们直接加上break。因为如果这棵树一开始就是大根堆，我们不需要做任何调整。我们接下来调试看下结果。

        完整代码实现：

public class Heap {
    //储存数据
    public int[] elem;
    //存放有效数据的个数
    public int usedSize;

    public Heap() {
        elem = new int[10];
    }

    //数组初始化
    public void Initial(int[] array) {
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            usedSize++;
        }
    }

    //堆的创建
    public void CreateHeap() {
        for (int parent = (usedSize - 1 - 1) / 2; parent >= 0; parent--) {
            shiftdown(parent, usedSize);
        }
    }

    private void shiftdown(int parent, int usedSize) {
        int child = 2 * parent + 1;
        while (child < usedSize) {
            if (child + 1 < usedSize && elem[child] < elem[child + 1]) {
                child++;
            }
            //走到这里，child下标一定是左右孩子最大值的下标
            if (elem[child] > elem[parent]) {
                //交换
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                parent = child;
                child = 2 * parent + 1;
            } else {
                break;
            }
        }
    }
}

public class Test {
    public static void main(String[] args) {
        int[] array = {27, 15, 19, 18, 28, 34, 65, 49, 25, 37};
        Heap newHeap = new Heap();
        newHeap.Initial(array);
        newHeap.CreateHeap();
    }
}

        这是创建大根堆，如果我们是创建小根堆，只需要比较值域的地方把大于小于号改成相反的就可以了。接下来我们思考一下向下调整的时间复杂度：从代码上来看，进行一层一层的交换，时间复杂度为，但我们不能光看代码，还需要进行推导。如果这棵树，最坏情况下是一棵满二叉树，我们假设树的高度为h，第1层共有1个结点，需要向下移动h-1层；第2层共有2个结点，需要向下移动h-2层；第3层共有4个结点，需要向下移动h-3层……每一层移动的时间加起来就是整棵树的时间复杂度：。利用错位相减可以算出，则时间复杂度为。

2.5. 堆的插入与删除

2.5.1. 堆的插入

        先将元素放⼊到底层空间中（注意：空间不够时需要扩容），并且需要进行调整，还要满足是大根堆（如下图所示）。我们可以模拟一下这个过程，可以采用向上调整的方式来实现。

        我们先写一个isFull方法来判断是不是满了，如果满了，就扩容。

    public boolean isFull() {
        return elem.length == usedSize;
    }

    public void offer(int val) {
        if (isFull()) {
            elem = Arrays.copyOf(elem, 2 * elem.length);
        }
        elem[usedSize] = val;
        //调整
        ShiftUp(usedSize);
        usedSize++;
    }

        对于向上转型，只要parent不是负数，就不断地向上调整。对于交换的代码，由于我们上面在向上转型里面已经实现父亲结点与孩子结点的交换，那我们也可以把这个交换方法抽象出来用。选中实现交换的代码，右键点击“Refactor”，再点击“Extract Method”就可以实现。

    private void swap(int parent, int child) {
        int tmp = elem[child];
        elem[child] = elem[parent];
        elem[parent] = tmp;
    }

    public void offer(int val) {
        if (isFull()) {
            elem = Arrays.copyOf(elem, 2 * elem.length);
        }
        elem[usedSize] = val;
        //调整
        ShiftUp(usedSize);
        usedSize++;
    }

    private void ShiftUp(int child) {
        int parent = (child - 1) / 2;
        while(parent >= 0){
            if(elem[child] > elem[parent]){
                swap(elem[child], elem[parent]);
                child = parent;
                parent = (child - 1) / 2;
            }else{
                break;
            }
        }
    }

        调试结果：

2.5.2. 堆的删除

        对于元素的删除，我们先删优先级最高的“65”，这个方法非常巧妙：我们先把"65"与最后一个结点下标的元素进行交换，再利用向下调整再变成大根堆（在这个过程中65不参与调整）。

    public int poll() {
        if(isEmpty()){
            return -1;
        }
        int OldValue = elem[0];
        usedSize--;
        swap(0,usedSize);
        ShiftDown(0,usedSize);
        return OldValue;
    }

    public boolean isEmpty() {
        return usedSize == 0;
    }