完全二叉树与堆的转换

「爱情、让人受尽委屈。」 2024-03-30 18:02 46阅读 0赞

#### 文章目录 ####

*  堆
 *   *  1.1基本介绍
     *  1.2 调整最小堆最大堆

## 堆 ##

### 1.1基本介绍 ###

1.实际上是一种**完全二叉树**，且某个节点的值总是**不大于**或者**不小于**其父节点的值（分别称为最大堆、最小堆）。

2.jdk1.8中优先级队列 PriorityQueue，底层即采用**堆**的数据结构存储，具有返回优先级最高的对象，添加新的对象的最基本操作。

3.堆底层使用数组实现（**顺序存储**），使用堆总是完全二叉树，这样不会出现数组中间出现 null 的情况。

如图基本结构：  
![在这里插入图片描述][8fd187f972814632933accf7dcf427a5.png]

### 1.2 调整最小堆最大堆 ###

将二叉树调整为小根堆或者大根堆  
思路：从**最后一个子树**开始，比较节点值的大小  
如图：调整前：  
![在这里插入图片描述][542e8bf01c96452cbdb05002d2216c37.png]  
从最后一个子树（usedSize-1）开始调整，每颗子树的左右孩子最大值与父亲节点比较。  
观察到父亲节点与usedSize关系  
![在这里插入图片描述][6a6bba3bd68b4200956f23f94a4c0d56.png]  
**parent = (usedSize-1-1)/2;**

调整后：  
![在这里插入图片描述][c21e40b9704b4611bfe3d0b6ece02124.png]  
**完整代码**：  
注：调整为大根堆，小根堆同理  
用向下调整方法建堆，如果左右子树满足堆的性质则只需要调整比较根节点  
即时间复杂度等于树的高度O(logN)，如果不满足则为O(N)即如下代码。

**代码整体思路**：  
1.声明一个固定大小的数组（假设），用于存储二叉树节点值。  
2.initElem()方法初始化数组，创建完全二叉树。  
3.createHeap()方法创建堆，只需要将创建好的二叉树，调整为最大或最小堆，从最后一个子树开始，调整。（找到最后一个非叶子节点与usedSize关系，可以遍历到所有非叶子节点，进行调整）  
4.shiftDown(in parent,int len)方法，对子树进行向下调整，parent父亲节点下标，len树结束下标，  
比较孩子节点与父亲节点的值，交换，将一个子树调整为大根堆

> parent = child;  
> child = 2\*parent+1;

继续将父亲，孩子节点向下移动，继续调整（由于createHeap是从最后一个非叶子节点开始到根节点，所所以当所有的子树均调整好时，会出现如第三步的变形，需要向下再次调整。  
![在这里插入图片描述][69d0900559254be0831b0b27b9730acb.png]

package demo7;
    
    /**
     * @author zq
     * 堆
     */
    public class TestHeap {
        
        public int[] elem;
        public int usedSize;
    
        public TestHeap(){
        
            this.elem = new int[10];
            //usedSize默认为零
        }
        //创建完全二叉树
        //array大小不超过10
        public void initElem (int[] array){
        
            for (int i = 0; i < array.length; i++) {
        
                elem[i] = array[i];
                usedSize++;
    
            }
        }
        //从最后一个子树（usedSize-1）开始调整，每颗子树的左右孩子最大值与父亲节点比较
        // 观察到父亲节点与usedSize关系
        public void createHeap(){
        
            for(int parent = (usedSize-1-1)/2;parent>=0;parent--){
        
               //由于每棵树结束下标不断变化，则采用usedSize最大的值
                shiftDown(parent,usedSize);
    
            }
        }
        //定义一个通用方法调整，
        // parent 父亲下标，len每棵树的结束下标
        private void shiftDown(int parent,int len){
        
            //定义一个cur指向孩子节点，左孩子节点下标 = 2*parent+1
           int child = 2*parent +1;
           //最起码有左孩子，数组从0开始
           while (child < len) {
        
               //有右孩子的情况下，先比较左右孩子节点,且保证不越界
               if (child + 1 < len && elem[child] < elem[child + 1]) {
        
                   child++;
               }
               //child下标指向左右孩子最大值
               if (elem[child] > elem[parent]) {
        
                   int temp = 0;
                   temp = elem[parent];
                   elem[parent] = elem[child];
                   elem[child] = temp;
    //               继续向下调整
                   parent = child;
                   child = 2*parent+1;
    
               }else {
        
                   break;
               }
           }
    
        }
    
    }

[8fd187f972814632933accf7dcf427a5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/d9dca32e96354a50ac0269814f0e50ed.png
[542e8bf01c96452cbdb05002d2216c37.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/0cca5dd8d06e4097a9e9cdbb6c91b62b.png
[6a6bba3bd68b4200956f23f94a4c0d56.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/93287c6c1fcf4dc296fc1ec043442615.png
[c21e40b9704b4611bfe3d0b6ece02124.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/4efa7b6cd9d24169bef09ed0ad8830dc.png
[69d0900559254be0831b0b27b9730acb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/7b83f3f63b324009867741018e05fa75.png