数据结构(Java):优先级队列(堆)&堆的模拟实现

时间:2024-07-19 07:53:14

目录

1、优先级队列

1.1 概念

1.2 PriorityQueue底层结构

2、 堆

2.1 堆的概念

 2.2 堆的存储结构

3、优先级队列(堆)的模拟实现

3.1 堆的创建

3.1.1 向下调整算法建完整堆

3.2 堆的插入 

3.2.1 向上调整算法

 3.3 堆的删除

3.4 堆排序


1、优先级队列

1.1 概念

对于队列而言,数据只能从队尾进,队头出,遵循着固定的先进先出原则。

而在某些特殊场景需求下,要求优先级高的元素先出队列,

在这种情况下,数据结构应该提供两个最基本的操作:

  • ①:不仅能添加新对象
  • ②:还能返回最高优先级对象。

这种数据结构就是优先级队列,Java也提供了PriorityQueue集合。 

1.2 PriorityQueue底层结构

PriorityQueue底层是堆这种数据结构,而堆实际就是在完全二叉树的基础上进行了一些调整,接下来,让我们来聊一聊堆到底是什么。


2、 堆

2.1 堆的概念

 所有元素按完全二叉树的顺序存储方式存储在一个一维数组中。

堆分为 大根堆与小根堆。

大根堆:每个节点都大于或等于其子节点。

小根堆:每个节点都小于或等于其子节点。


 2.2 堆的存储结构

我们已知堆为一棵完全二叉树,故采用顺序的方式存储在数组中。

而对于我们之前所学的二叉树,为什么没有采用顺序存储而是采用链式存储呢?

因为二叉树并非都为完全二叉树,若采用顺序存储会造成空间浪费:

因为堆采用顺序的方式进行存储,且为完全二叉树,故具有以下性质:

  1. 孩子节点下标为i,则其父亲节点下标为(i - 1)/2
  2. 父亲下标为i,则其左孩子下标为2i+1(2i+1<节点总数的情况下,否则无左孩子)
  3. 父亲下标为i,则其右孩子下标为2i+2(2i+2<节点总数的情况下,否则无右孩子)

3、优先级队列(堆)的模拟实现

注:下文中代码实现的为大根堆

3.1 堆的创建

 向下调整算法

向下调整算法:选出其左右孩子中值较小值元素(建大堆就选较大元素,建小堆就选较小元素,这里以建小堆为例),将这个元素和根节点进行比较,若比根节点还小,就和根节点交换,交换后可能导致子树不满足堆的性质,因此需要继续向下调整。

注意:向下调整算法的使用,必须要求其左右子树必须为大根堆或者小根堆!!!

向下调整算法的时间复杂度为:O(logN),因为最坏情况是从根一路比较到叶子,比较的次数即为完全二叉树的高度次。

3.1.1 向下调整算法建完整堆

我们给出一组数据:{ 27,15,19,18,28,34,65,49,25,37 },要想将这组数据建成堆,我们可以使用向下调整法建堆。

而一组乱序数据其左右子树是不为堆的,那就需要通过向下调整算法从倒数第一个非叶子节点(下标为(数组.length-1-1)/2 )开始建堆,直到将整棵树建成堆。

建堆的时间复杂度为:O(N)!!!,

什么不是O(N*logN)呢?这里给出解释:

向下调整整体建堆代码:

/**
     * 建堆整体时间复杂度:O(N)
     */
    public void createHeap() {
        //从倒数第一个飞非叶子节点开始建堆
        int parent = (this.usedSize - 1 - 1)/2;
        while (parent >= 0) {//O(N)
            siftDown(parent,this.usedSize);
            parent--;
        }
    }
    /**
     *向下调整算法
     * 时间复杂度:O(logN)
     * @param parent 向下调整的起始位置,即根节点
     * @param usedSize 标定调整的结束 若算出的孩子节点坐标>=usedSize时,说明已调整完成
     */
    private void siftDown(int parent, int usedSize) {
        int child = parent*2+1;
        //当没有孩子节点时,说明向下调整完成
        while (child < usedSize) {
            //当右孩子存在时,选出左右孩子的最大值(建大堆)
            if (child + 1 < usedSize) {
                if (elem[child] < elem[child + 1]) {
                    child = child + 1;
                }
            }
            //和根节点进行比较
            if (elem[child] > elem[parent]) {
                swap(elem, parent, child);
                parent = child;
                child = parent*2+1;
            }else {
                //若根节点大,说明已是大堆,break结束
                break;
            }
        }
    }

3.2 堆的插入 

插入数据总共有两个步骤:

  1. 将新元素插入堆的末尾(插入后不再为堆)
  2. 使用向上调整算法调整为堆 

3.2.1 向上调整算法

(这里以建小堆为例):将元素插入到堆的末尾后,和根节点进行比较,如果比根节点还小就和根节点换,继续向上调整,直至满足堆的性质。如果没有根节点小,说明此时已满足堆的性质,调整完成。

时间复杂度:O(logN)

插入元素代码:

/**
     * 插入元素
     * 时间复杂度:O(logN)
     * @param x:新插入元素的值
     */
    public void offer(int x) {
        if (isFull()) {
            grow();
        }
        elem[usedSize] = x;
        siftUp(usedSize);
        usedSize++;
    }

    /**
     * 向下调整算法
     * @param childIndex:新插入元素的下标
     */
    public void siftUp(int childIndex) {
        //找到新节点的父节点的下标
        int parent = (childIndex - 1)/2;
        //parent为负数时,说明调整完成(最坏)
        while (parent >= 0) {
            if (elem[parent] < elem[childIndex]) {
                swap(elem,parent,childIndex);
                childIndex = parent;
                parent = (childIndex - 1)/2;
            }else {
                break;
            }
        }
    }
    /**
     * 如果堆底层的数组满了,就扩容
     */
    private void grow() {
        this.elem = Arrays.copyOf(elem,elem.length*2);
    }

向上调整算法建堆【拓展】 

故我们也可以一个一个的插入元素(使用向上调整算法)来建堆,但是不推荐,因为时间复杂度比向下调整算法建堆要大,为:O(N*logN)

其实主要原因就是:最后一层的元素是最多的,都要一个个向上调整


 3.3 堆的删除

堆的删除一定删除的是堆顶元素。

故,删除元素的思想很简单,即:

  1.  将堆顶元素和堆中最后一个元素交换
  2.  将堆中有效数据个数(usedSize)减一
  3.  对堆顶元素进行向下调整(只需要调整0下标就可以了)

 堆删除代码:

/**
     * 删除堆元素
     */
    public void poll() {
        if (isEmpty()) {
            //如果堆为空,返回
            return;
        }
        //交换堆顶和最后一个元素
        swap(elem,0,usedSize-1);
        //堆元素有效个数-1
        usedSize--;
        //只向下调整0下标即可
        siftDown(0,usedSize);
    }

3.4 堆排序

若要升序排列,要建大根堆;若要降序排列,就要建小根堆。

以排升序为例:若要排升序,则为大堆,排序过程如下:

  1. 将堆顶元素和堆末元素交换,有效数据个数减一(因为堆顶元素为最大值元素,此时最大值元素已来到数组末尾)
  2. 将0下标处向下调整,重新调整为大堆
  3. 继续将堆顶元素和堆末元素交换,有效数据个数减一(堆顶元素为次大值元素,此时次大值元素已来到数组末尾倒数二个位置处)
  4. 将0下标处向下调整,重新调整为大堆
  5. 重复以上过程,直至只剩一个元素的时候,此时数组已有序且为升序排列

堆排序 排升序代码 :

/**
     * 堆排序
     */
    public void heapSort() {
        if (isEmpty()) {
            return;
        }
        int end = usedSize-1;
        while (end > 0) {
            swap(elem,0,end);
            siftDown(0,end);
            end--;
        }
    }

相关文章