Java数据结构 | 模拟实现优先级队列

目录

一、前言

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

2.1 堆的概念

2.2 堆的性质

2.3 堆的存储方式

2.4 堆的创建

---

一、前言

在前面我们学习过队列，队列是一种先进先出(FIFO)的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队列时，可能需要优先级高的元素先出队列，该中场景下，使用队列显然不合适，比如：在手机上玩游戏的时候，如果有来电，那么系统应该优先处理打进来的电话。

在这种情况下，我们的数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)。

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

JDK1.8中的PriorityQueue底层使用了堆的数据结构，而堆实际就是在完全二叉树的基础之上进行了一些元素的调整。

2.1 堆的概念

如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中，并满足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为 小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

2.2 堆的性质

• 堆中某个节点的值总是不大于或不小于其父节点的值；

• 堆总是一棵完全二叉树。

与二叉搜索树不同，堆的左右节点都小于根节点，而左右节点的值没有大小关系

2.3 堆的存储方式

堆是一棵完全二叉树，因此可以采用层序的规则来顺序存储

注意：对于非完全二叉树，则不适合使用顺序方式进行存储，因为为了能够还原二叉树空间中必须要存储空节点，就会导致空间利用率比较低

将元素存储到数组中后，可以根据二叉树章节的性质5对树进行还原。假设i为节点在数组中的下标，则有：

• 如果i为0，则i表示的节点为根节点，否则i节点的双亲节点为 (i - 1)/2

• 如果2 * i + 1 小于节点个数，则节点i的左孩子下标为2 * i + 1，否则没有左孩子

• 如果2 * i + 2 小于节点个数，则节点i的右孩子下标为2 * i + 2，否则没有右孩子

2.4 堆的创建

• 堆的向下调整

条件：必须左右子树已经是堆了才能调整

对于集合{ 27,15,19,18,28,34,65,49,25,37 }中的数据，如果将其创建成堆呢？

观察这棵树可以发现，根节点的左右两边已经满足小根堆的性质，只需将根节点进行向下调整即可

调整过程：

• 将此二叉树的根节点设置为 parent 节点 ，

• 比较 parent 节点的孩子节点的值，将孩子节点中的较小的节点设置为 child 节点

  • 初始状态

• 比较 parent 节点和 child 节点的值的大小

  • 若 parent > child , 则不满足小根堆的性质，将两者进行交换。

  • 若 parent < child , 满足小根堆的性质，不进行交换，调整结束。

• 每次交换后，更新child 和parent的位置， parent =child，child = 2 *parent+1;

• 代码实现： 时间复杂度： O(logN) — parent固定,child 每次 x 2

//    小根堆的向下调整(满足parent的左子树和右子树已经是堆了)
    public void shiftDown(int parent,int len){
        int child = 2*parent +1;
//        必须保证右左孩子
        while(child < len){
//            找到左右孩子的最小值
            if(child +1 < len && elem[child] > elem[child+1]){
                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;
            }
        }
    }

针对向下调整的思路，我们可以进行建堆，将一个数组建造成堆，从倒数第一个非叶子节点开始，从后往前遍历数组，依次进行向下调整，就可以得到一个小根堆

例：将以下数组[9,5,2,7,3,6,8] 建成一个小根堆

此时根节点的左右孩子两边的树均满足小根堆的特点，只需要调整以9为根的树向下调整即可，调整过程与结果如下

最后的结果即

• 代码实现

时间复杂度：建堆的时间复杂度为 O(n) （复杂的数学计算）

    public void crearHeap(){
//        最后一个节点的下标为  i  = usedSize -1
//         (i - 1) / 2 即为最后一个非叶子节点的下标
        for(int parent = (usedSize-1-1)/2; parent >= 0;parent--){
           shiftDown(parent,usedSize);
          //对每一个非叶子节点进行向下调整
        }
    }

usedsize - 即为最后一个叶子节点的下标，((usedsize -1) - 1) / 2 即为最后一个非叶子节点的下标

• 堆的向上调整

当我们进行元素的插入时，仍要保证这个堆是一个大根堆，则需要对堆进行向上调整

将堆进行向上调整的步骤

• 将插入的元素即最后一个叶子节点设置为 child ,其父亲节点设置为parent = (child-1) /2

• 当child > parent 时 ， 不满足大根堆的性质，将父亲节点的值与叶子节点的值进行交换

• 当child

调整完成之后重新更新parent 和 child 的位置，即 child = parent , parent = 2 * child +1

向上调整为大根堆的代码实现如下：

  public void shiftUp(int child){
        int parent = (child-1) /2;
        while(child > 0){
            if(elem[child] > elem[parent]){
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                child = parent;
                parent = (child -1)/2;
            }else {
                break;
            }
        }
    }

• 堆中插入一个元素时，代码实现

public void offer(int val){
//如果堆为满，则对数组进行扩容
        if(isFull()){
            elem = Arrays.copyOf(elem,2*elem.length);
        }
 //将插入的元素设置为堆的最后一个元素
        this.elem[usedSize] = val;
        usedSize++;
 //将堆中元素进行向上调整
        shiftUp(usedSize-1);
    }
     public boolean isFull(){
        return elem.length == usedSize;
    }

• 堆的删除（删除堆顶元素）

  • 将堆顶元素与队中堆中最后一个节点的值进行交换

  • 将堆中的元素值减少一个

  • 对堆中的元素进行向下调整

代码实现如下：

public int pop(){
        if(isEmpty()){
            return -1;
        }
        int tmp = elem[0];
        elem[0] = elem[usedSize -1];
        elem[usedSize -1] = tmp;
        usedSize--;
    //将堆中元素进行向下调整
        shiftDown(0,usedSize);
        return tmp;
    }

• 使用堆模拟实现优先级队列

public class TestHeap {
    public int[] elem;
​
    public int usedSize;
​
    public static int DEFAULT_SIZE = 10 ;
​
    public TestHeap() {
        this.elem = new int[DEFAULT_SIZE];
    }
​
    public void init(int[] array){
        for(int i = 0; i < array.length;i++){
            elem[i] = array[i];
            usedSize++;
        }
    }
//   建堆的时间复杂度为O(n)
    public void crearHeap(){
//        最后一个节点的下标为  i  = usedSize -1
//         (i - 1) / 2 即为父亲节点的下标
        for(int parent = (usedSize-1-1)/2; parent >= 0;parent--){
           shiftDown(parent,usedSize);
        }
    }
    /**
     *
     * @param parent 每棵子树的根节点
     * @param len 每棵子树的
     * 时间复杂度:O(log(n))
     */
//    小根堆的向下调整(满足parent的左子树和右子树已经是堆了)
    public void shiftDown(int parent,int len){
        int child = 2*parent +1;
//        必须保证右左孩子
        while(child < len){
//            找到左右孩子的最小值
            if(child +1 < len && elem[child] > elem[child+1]){
                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 void offer(int val){
        if(isFull()){
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        this.elem[usedSize] = val;
        usedSize++;
        shiftUp(usedSize-1);
    }
//    向上调整
        public void shiftUp(int child){
        int parent = (child-1) /2;
        while(child > 0){
            if(elem[child] > elem[parent]){
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                child = parent;
                parent = (child -1)/2;
            }else {
                break;
            }
        }
    }
    public boolean isFull(){
        return elem.length == usedSize;
    }
    public boolean isEmpty(){
        return usedSize == 0;
    }
    public int pop(){
        if(isEmpty()){
            return -1;
        }
        int tmp = elem[0];
        elem[0] = elem[usedSize -1];
        elem[usedSize -1] = tmp;
        usedSize--;
        shiftDown(0,usedSize);
        return tmp;
    }
    public int peek(){
        if(isEmpty()){
            return -1;
        }
        return elem[0];
    }
}