数据结构之堆

ゝ一纸荒年。 2024-04-03 11:42 68阅读 0赞

## 系列文章目录 ##

[数据结构之PriorityQueue源码及特性分析 (大小根堆转换、扩容)\_crazy\_xieyi的博客-CSDN博客][PriorityQueue_ _crazy_xieyi_-CSDN]

--------------------

文章目录

*  **前言**
 *  **一、堆是什么？**
 *  **二、堆的存储方式是什么？**
 *  **三、堆是怎么创建的？**
 *  **四、建堆的时间复杂度是多少？**
 *  **五、堆是怎么进行插入和删除元素的？**
 *  **六、用堆模拟实现优先级队列**

--------------------

## 前言 ##

**队列是一种先进先出** **的数据结构**，但有些情况下， **操作的数据可能带有优先级，一般出队**

**列时，可能需要优先级高的元素先出队列**，这个时候就需要带有优先级的数据结构，这种数据结构就是 **优先级队列** **(PriorityQueue)** **。**

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

--------------------

**一、堆是什么？**

把所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，如果所有根节点都不大于左右孩子，则为小根堆；如果所有根节点都不小于左右孩子，则为大根堆。

**堆的性质如下：**

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

2.堆总是一棵完全二叉树

![f18ead66417b48d789612e73e90ed7c2.png][]

##  ##

### **二、堆的存储方式是什么？** ###

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

![a7bb880c0ddf4060beb60af79f220126.png][]

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

### **三、堆是怎么创建的？（大根堆）** ###

1. 让parent标记需要调整的节点，child标记parent的左孩子(注意：parent如果有孩子一定先是有左孩子)

2. 如果parent的左孩子存在，即:child < usedsize， 进行以下操作，直到parent的左孩子不存在。

parent右孩子是否存在，存在找到左右孩子中最大的孩子；

将parent与较大的孩子child比较，如果：

parent大于较大的孩子child，调整结束

否则：交换parent与较大的孩子child，交换完成之后，parent = child；child = parent\*2+1; 然后继续2。

public void createHeap(){
            for (int parent = (usedSize-1-1)/2; parent >= 0 ; parent--) {
                shiftDown(parent,usedSize);
            }
        }
    
        /**
         * 每个根节点向下调整
         * @param parent     父节点
         * @param usedSize  调整的结束位置不能超过
         */
        public void shiftDown(int parent, int usedSize){
            int child = parent*2 + 1;
            while (child < usedSize){   //保证有左孩子
                if(child+1 < usedSize && elem[child] < elem[child+1]){ //保证有右孩子且大于左孩子
                    child++;
                }
    
                if (elem[child] > elem[parent]){
                    int temp = elem[child];
                    elem[child] = elem[parent];
                    elem[parent] = temp;
                    parent = child;
                    child = parent*2 +1;
                }else {
                    break;
                }
            }
        }

### **四、建堆的时间复杂度是多少？O(n)** ###

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：（向下调整）

![28bb5c8812194a1da2de5e34b6f01e13.png][]

### **五、堆是怎么进行插入和删除元素的？** ###

堆的插入总共需要两个步骤：  
1. 先将元素放入到底层空间中(注意：空间不够时需要扩容)  
2. 将最后新插入的节点向上调整，直到满足堆的性质

public void offer(int val){
            if (isFull()){
                elem = Arrays.copyOf(elem,2*elem.length);
            }
            elem[usedSize] = val;
            usedSize++;
            shiftUp(usedSize-1);
        }
        private void shiftUp(int child){
            int parent = (child - 1)/2;
            while (parent >= 0)
            if (elem[child] > elem[parent]){
                int temp = elem[parent];
                elem[parent] = elem[child];
                elem[child] = temp;
                child = parent;
                parent = (child - 1)/2;
            }else {
                break;
            }
        }
        public boolean isFull(){
            return elem.length == usedSize;
         }

**堆的删除**一定删除的是堆顶元素。具体如下：  
1. 将堆顶元素对堆中最后一个元素交换  
2. 将堆中有效数据个数减少一个  
3. 对堆顶元素进行向下调整

public int pop(){
            if (isEmpty()){
                return -1;
            }
            int temp = elem[0];
            elem[0] = elem[usedSize-1];
            elem[usedSize-1] = temp;
            usedSize--;
            shiftDown(0,usedSize);
            return temp;
         }
         public boolean isEmpty(){
            return usedSize == 0;
         }
        /**
         * 每个根节点向下调整
         * @param parent     父节点
         * @param usedSize  调整的结束位置不能超过
         */
        public void shiftDown(int parent, int usedSize){
            int child = parent*2 + 1;
            while (child < usedSize){   //保证有左孩子
                if(child+1 < usedSize && elem[child] < elem[child+1]){ //保证有右孩子且大于左孩子
                    child++;
                }
    
                if (elem[child] > elem[parent]){
                    int temp = elem[child];
                    elem[child] = elem[parent];
                    elem[parent] = temp;
                    parent = child;
                    child = parent*2 +1;
                }else {
                    break;
                }
            }
        }

### **六、用堆模拟实现优先级队列** ###

public class MyPriorityQueue {
        public int[] elem;
        public int usedSize;
    
        public MyPriorityQueue() {
            this.elem = new int[11];
        }
    
        /**
         * 建堆的时间复杂度：
         *
         * @param array
         */
        public void createHeap(int[] array) {
            for (int i = 0; i < array.length; i++) {
                elem[i] = array[i];
                usedSize++;
            }
            int parent = (usedSize-1-1)/2;
            for (int i = parent; i >= 0; i--) {
                shiftDown(parent,usedSize);
            }
        }
    
        /**
         *
         * @param root 是每棵子树的根节点的下标
         * @param len  是每棵子树调整结束的结束条件
         * 向下调整的时间复杂度：O(logn)
         */
        private void shiftDown(int root,int len) {
            int child = root*2 + 1;
            while (elem[child] > elem[root]){
                if (child+1 < len && elem[child] < elem[child+1]){
                    child++;
                }
                if (elem[child] > elem[root]){
                    int temp = elem[child];
                    elem[child] = elem[root];
                    elem[root] = temp;
                    child = root;
                    root = (child-1)/2;
                }else {
                    break;
                }
            }
        }
    
    
        /**
         * 入队：仍然要保持是大根堆
         * @param val
         */
        public void push(int val) {
            if (isFull()){
                elem = Arrays.copyOf(elem,2*elem.length);
            }
            elem[usedSize] = val;
            usedSize++;
            shiftUp(usedSize-1);
        }
    
        private void shiftUp(int child) {
           int parent = (child-1)/2;
           while (parent >= 0){
               if (elem[child] > elem[parent]){
                   int temp = elem[child];
                   elem[child] = elem[parent];
                   elem[parent] = temp;
                   child = parent;
                   parent = (child-1)/2;
               }else {
                   break;
               }
           }
        }
    
        public boolean isFull() {
            return usedSize == elem.length;
        }
    
        /**
         * 出队【删除】：每次删除的都是优先级高的元素
         * 仍然要保持是大根堆
         */
        public void pollHeap() {
            if (isEmpty()){
                return;
            }
            int temp = elem[0];
            elem[0] = elem[usedSize-1];
            elem[usedSize-1] = temp;
            usedSize--;
            shiftDown(0,usedSize);
        }
    
        public boolean isEmpty() {
            return usedSize == 0;
        }
    
        /**
         * 获取堆顶元素
         * @return
         */
        public int peekHeap() {
            if (isEmpty()){
                System.out.println("队列为空！");
                return -1;
            }
            return elem[0];
        }
    }

[PriorityQueue_ _crazy_xieyi_-CSDN]: https://blog.csdn.net/crazy_xieyi/article/details/127278362?spm=1001.2014.3001.5501
[f18ead66417b48d789612e73e90ed7c2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/a1abfeef562b4d25a3d3b68c6e1357e4.png
[a7bb880c0ddf4060beb60af79f220126.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/b90cfffbbf154a46bdce2d74b3f549e1.png
[28bb5c8812194a1da2de5e34b6f01e13.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/b3a94b4b49c44ddf81874d6fc521e41f.png