【优先级队列 之 堆的实现】

发布时间:2024年01月23日


前言


优先级队列 PriorityQueue

概念:对列是先进先出的的数据结构,但有些情况,数据可能带有优先级,一般出队列时,可能需要优先级高的元素先出队列。所以像这种情况用队列不太合适:在手机上玩游戏时,如果有来电,系统应该优先处理打进来的电话。以前是来电显示充满整个画面,现在变成了一个小窗。

优先队列的模拟实现

PriorityQueue的底层使用了堆这种数据结构(PriorityQueue底层实现是一个完全二叉树,完全二叉树又分为大根堆和小根堆)

概念:
小根堆:根节点比左右孩子都小。只考虑根和左右节点的关系,不考虑左右节点的哪个大。
大根堆:根节点比左右孩子都大

堆的储存方式

在这里插入图片描述
将元素存储到数组中后,可以根据二叉树章节的性质5对树进行还原。假设为节点在数组中的下标,则有: 如果为0,则表示的节点为根节点,否则节点的双亲节点为(i 1)/2
●如果2i+ 1小于节点个数,则节点的左孩子下标为2 门中1,否则没有左孩了
●如果2
i+2小于节点个数,则节点的右孩子下标为2
1+ 2,否则没有右孩子

堆的创建

  1. 让parent标记需要调整的节点,child标记parent的左孩子(注意: parent如果有孩子一 定先是有左孩子)
  2. 如果parent的左孩子存在,即:child < size,进行以下操作, 直到parent的左孩子不存在
    parent右孩子是否存在,存在找到左右孩子中最大的孩子,让child进行标记
  3. 将parent 与较大的孩子child比较,如果:
    parent小于较大的孩子child,交换parent与较大的孩子child,交换完成之后,parent中小的元素向下移动,并继续向下调整,即parent = child; child = parent*2+1;然后继续
    否则:退出循环。
public class TestHeap {
    //创建一个数组
    public int[] elem;
    public int useSize;//有效元素

    //构造方法给elem分配内存
    public TestHeap() {
        this.elem = new int[10];
    }

    //初始化elem数组,给elem传入元素
    public void initElem(int[] array){
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            useSize++;
        }
    }

    /**
     * 创建大根堆的代码
     */
    public void createHeap(){
        for (int parent =(useSize-1-1)/2 ; parent >=0 ; parent--) {
            siftDown(parent,useSize);

        }
    }

    /**
     * 向下调整
     * @param parent
     * @param len
     */
     //让child标记根的左孩子,如果左孩子大于数组长度则进行下面操作
    // 如果右孩子小于长度并且左孩子的值小于右孩子的值,让左孩子移到右孩子上
    private void siftDown(int parent,int len){
        int child = 2*parent+1;
        while(child < len){
            if (child+1 < len && elem[child] < elem[child+1]){
                child = 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 class Test {
    public static void main(String[] args) {
        TestHeap testHeap = new TestHeap();
        int[] array={27,15,19,18,28,34,65,49,25,37};
        testHeap.initElem(array);
        testHeap.createHeap();
        System.out.println("========");
    }
}

建堆的时间复杂度

在这里插入图片描述
因此:建堆的时间复杂度是0(N)

堆的插入与删除

堆的插入:
在这里插入图片描述

    private void swap(int i,int j){
        int tmp = elem[i];
        elem[i] = elem[j];
        elem[j] = tmp;
    }

    //向上调整
    public void push(int val){
        if(isFull()){
            elem = Arrays.copyOf(elem,elem.length*2);
        }
        elem[usedSize] = val;
        siftUp(usedSize);
        usedSize++;
    }
    public boolean isFull(){
        return usedSize == elem.length;
    }
    public void siftUp(int child){
        int parent = (child-1)/2;
        while(child > 0){
            if (elem[child] > parent){
                swap(child,parent);
                child = parent;
                parent = (child-1)/2;
            }else{
                break;
            }
        }
    }

堆的删除
注意:这里的删除指的是删除堆顶的元素

  1. 将0下标的的堆顶元素和堆的最后一个元素交换
  2. 将堆的有效个数usedSize–
  3. 对堆进行向下调整
    //删除堆顶元素
    public int pop(){
        if (empty()){
            return -1;
        }
        int oldVal = elem[0];
        swap(0,usedSize-1);
        usedSize--;
        siftDown(0,usedSize);
        return oldVal;
    }
    public boolean empty(){
        return usedSize == 0;
    }

总结

本章节学习如何实现一个堆,如何运用到向上调整,向下调整。

文章来源:https://blog.csdn.net/2301_76496134/article/details/135735451
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。