【数据结构】堆和优先级队列_堆和优先队列

作者：繁依Fanyi0 | 2024-08-05 13:25:25

踩

堆和优先队列

一、堆

优先级队列：入队和队列是一样的默认都是队尾入队，出队的时候按照优先级出队，优先级相同的元素按照FIFO出队，优先级高的元素首先出队。

优先级队列的两大特点：

（1）按照优先级出队。

（2）优先级高的元素首先出队。

一、堆

堆是优先级队列背后的数据结构。

我们此处讲得堆其实是二叉堆，基于完全二叉树的二叉堆，广义的堆还有多叉堆（多叉树）。

还有索引堆，普通的对只知道堆顶元素的大小，索引堆可以取得堆中任意位置元素=》在图的最小生成树prim算法和最短路径Diijkstra算法的优化中使用索引堆。

1.1堆的特点

（1）堆首先是完全二叉树，一般使用动态数组（不用存储null结点，元素都靠左排序）存储具体元素。

（2）元素元素的值：

堆中任意一个节点的值<=父节点值（最大堆/大根堆）数据结点>=子树节点。

堆中任意一个节点的值>=父节点值（最小堆/小根堆）数据结点<=子树节点，JDK中的优先级队列默认是最小堆的实现。

在堆中，结点值的大小和节点所处的层次没有明确关系。

关于完全二叉树的节点编号：根据编号以及索引关系，在数据中寻找某一个结点的子节点与父节点编号和索引位置，都从0开始编号，若某个节点的编号（索引）为x。

性质1：判断父节点：

如何判定父结点存在，若存在，索引是多少？parent（x） = （x-1）/2。

当x>0，则一定存在父节点（在二叉树中，只有根节点（根节点索引为0）没有父节点），且父节点的编号为（x-1）/2。

性质2：判断左子树结点

如何判断当前节点x还存在左子树结点？左子树结点编号是多少》

当前完全二叉树的结点个数<=数组最大长度，左子树结点编号为2x+1<size（当前数组种有效的元素个数）。

性质3：判断右子树结点：

右子树结点编号为2x+2<size。

1.2如何构造一个最大堆

（1）最大堆的构造以及常用方法的实现

创建一个线性表的数组，然后创建一个int类型的size来判断存储了多少个数据。

默认状态数组长度为10，也可以通过有参构造自定义数组的长度。

创建三个判断父节点左右节点坐标的方法以及判空方法和输出方法。


public class MaxHeap {
    private List<Integer> arr;
    private int size;
    public MaxHeap() {
        this(10);
    }
    public MaxHeap(int capacity) {
        this.arr = new ArrayList<>(capacity);
    }
    private int parent(int k){
        return (k-1)>>1;
    }
    private int leftChild(int k){
        return (k<<1)+1;
    }
    private int rightChild(int k) {
        return (k << 1) + 2;
    }
    public boolean isEmpty() {
        return size == 0;
    }
    public String toString() {
        return arr.toString();
    }
}

（2）添加操作

尾插方法很简单直接调用线性表的add方法即可，然后size++，在调用我们的siftUp方法。

任意数组都可以看做一颗完全二叉树，因此向堆中插入一个数据，就相当于在数组中插入一个数据（默认尾插）。

siftUp（上浮）不断比较插入后的元素和其父节点的值大小关系，若当前节点值>父节点值，交换他俩元素顺序，直到这个元素落在了正确位置。结束条件：要么此时k==0，已经走到了树根节点，要么此刻arr[k]<=ar

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/932624