• 优先级队列的模拟实现


    1. 优先级队列的概念

    队列是一种先进先出 (FIFO) 的数据结构 ,但有些情况下, 操作的数据可能带有优先级,一般出队 列时,可能需要优先级高的元素先出队列 在这种情况下, 数据结构应该提供两个最基本的操作,一个是返回最高优先级对象,一个是添加新的对象 。这种数 据结构就是 优先级队列 (Priority Queue)

    1.1堆的概念

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

    以大根堆为例:

    1.2堆的性质

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

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

     1.3堆的存储方式

    从堆的概念可知,堆是一棵完全二叉树,因此可以层序的规则采用顺序的方式来高效存储

    注意: 对于非完全二叉树,则不适合使用顺序方式进行存储,因为为了能够还原二叉树,空间中必须要存储空节 点,就会导致空间利用率比较低
    将元素存储到数组中后, 假设 i 为节点在数组中的下标,则有:
    如果 i 0 ,则 i 表示的节点为根节点,否则 i 节点的双亲节点为 (i - 1)/2
    如果 2 * i + 1 小于节点个数,则节点 i 的左孩子下标为 2 * i + 1 ,否则没有左孩子
    如果 2 * i + 2 小于节点个数,则节点 i 的右孩子下标为 2 * i + 2 ,否则没有右孩子

    2. 堆的创建

    1. public class TextHeap {
    2. public int[] arr;
    3. public int size;
    4. public TextHeap(int[] arr) {
    5. this.arr = arr;
    6. size=arr.length;
    7. }
    8. public void createheap(){
    9. for (int parent = (size-1-1)/2; parent >=0 ; parent--) {
    10. shiftDown(parent,size);
    11. }
    12. }
    13. private void shiftDown(int parent,int len){
    14. int child=2*parent+1;
    15. while(child
    16. if(child+11]>arr[child]){
    17. child++;
    18. }
    19. if(arr[parent]
    20. int tmp=arr[parent];
    21. arr[parent]=arr[child];
    22. arr[child]=tmp;
    23. parent=child;
    24. child=2*parent+1;
    25. }else {
    26. break;
    27. }
    28. }
    29. }
    30. }

    2.1堆的创建代码解析

    向下过程(以大根堆为例):

    1. 让parent标记需要调整的节点,child标记parent的左孩子(注意:parent如果有孩子一定先是有左孩子)
    2. 如果parent的左孩子存在,即:child < size, 进行以下操作,直到parent的左孩子不存在
    3. parent右孩子是否存在,存在找到左右孩子中最大的孩子,让child进行标将parent与较大的孩子child比较。

      如果parent大于较大的孩子child,调整结束。
      否则:交换parent与较大的孩子child,交换完成之后,parent中大的元素向下移动,可能导致子树不满足对的性质,因此需要继续向下调整即parent = child;child = parent*2+1; 然后继续(2)。

     2.2建堆的时间复杂度

     2.3堆的插入

    堆的插入总共需要两个步骤:
    1. 先将元素放入到底层空间中 ( 注意:空间不够时需要扩容 )。
    2. 将最后新插入的节点向上调整,直到满足堆的性质。
    代码:
    1. public void shiftUp(int child){
    2. int parent=(child-1)/2;
    3. while(child>0){
    4. if(arr[child]>arr[parent]){
    5. int tmp = arr[parent];
    6. arr[parent] = arr[child];
    7. arr[child] = tmp;
    8. child=parent;
    9. parent=(child-1)/2;
    10. }else {
    11. break;
    12. }
    13. }
    14. }
    15. public void offer(int val) {
    16. if (isfull()) {
    17. arr = Arrays.copyOf(arr, arr.length * 2);
    18. }
    19. arr[size++] = val;
    20. shiftUp(size-1);
    21. }
    22. public boolean isfull() {
    23. return arr.length == size;
    24. }

    从0开始插入建堆的时间复杂度

    2.4 堆的删除

    注意:堆的删除一定删除的是堆顶元素。 具体如下:
    1. 将堆顶元素对堆中最后一个元素交换
    2. 将堆中有效数据个数减少一个
    3. 对堆顶元素进行向下调整
    代码:
    1. public boolean empty() {
    2. return 0 == size;
    3. }
    4. public void pop(){
    5. if (empty()){
    6. return;
    7. }
    8. int tmp = arr[0];
    9. arr[0] = arr[size-1];
    10. arr[size-1] = tmp;
    11. size--;
    12. shiftDown(0,size);
    13. }

    2.5常见习题

    1. 下列关键字序列为堆的是 :()
    A: 100,60,70,50,32,65                B: 60,70,65,50,32,100               C: 65,100,70,32,50,60
    D: 70,65,100,32,50,60                E: 32,50,100,70,65,60               F: 50,100,70,65,60,32
    解析:
    答案:A
    B为啥错如下,其他同理。
    2. 已知小根堆为 8,15,10,21,34,16,12 ,删除关键字 8 之后需重建堆,在此过程中,关键字之间的比较次数是 ()
    A: 1            B: 2             C: 3           D: 4
    解析:
    答案:C

     3.最小堆[0,3,2,5,7,4,6,8],在删除堆顶元素0之后,其结果是()

    A: [3 2 5 7 4 6 8]                         B: [2 3 5 7 4 6 8]
    C: [2 3 4 5 7 8 6]                         D: [2 3 4 5 6 7 8]
    解析:
    答案:C

    以上为我个人的小分享,如有问题,欢迎讨论!!! 

    都看到这了,不如关注一下,给个免费的赞 

     

  • 相关阅读:
    SpringCloud Alibaba——精读Nacos+CMDB+核心源码阅读(7w字长篇)
    2023年腾讯云双十一活动攻略整理汇总
    如何查看Debian Linux的内核版本
    用C语言解决三个整数比大小,x,y,z三个整数求最小整数,从键盘上输入3个不同的整数×,y,Z,请设计一个算法找出其中最小的数,并画出流程图。
    3.1 Go语言中的函数与方法
    PyCharm 2022.2.1 opencv 4.6.0 安装与运行cv2 例程
    如何判断用户的密码是否为强密码?
    Python 用相对名称来导入包中的子模块
    Xshell连接Ubuntu详细过程
    EasyExcel的简单读取操作
  • 原文地址:https://blog.csdn.net/WHabc2002/article/details/133493354