Java实现堆的创建及相关操作

Love The Way You Lie 2024-03-27 13:27 62阅读 0赞

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

*  堆
 *   *  1.堆的创建
     *  2. 堆的插入
     *   *  2.1 原理
         *  2.2 代码
     *  3.堆的删除
     *   *  3.1原理
         *  3.2 代码
     *  4.获取堆顶元素

## 堆 ##

### 1.堆的创建 ###

原理：  
由于堆实际上是完全二叉树的变形，且二叉树某个节点的值总是不大于或者不小于其父节点的值（分别称为最大堆、最小堆）。  
所以，我们通过先建立一个完全二叉树，通过向下调整，将二叉树每个节点满足不大于或不小于其父节点的值。  
详情与代码见博客：[完全二叉树与堆的转换][Link 1]

### 2. 堆的插入 ###

#### 2.1 原理 ####

1.将插入的数存入到数组最后，也就是最后一个节点，由于堆的性质，我们需要调整堆的结构，直插入了一个节点，只需向上调整，将最后一个节点的值不断向上比较，就能确定下堆。  
2.时间复杂度：O(logN)

#### 2.2 代码 ####

/*
        堆的插入
        child 插入节点下标
         */
        public void shiftUp(int child){
        
            int parent = (child -1)/2;
            while(child >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 void offer(int val){
        
            if (isFull()){
        
                //扩容
                elem = Arrays.copyOf(elem,2*elem.length);
            }
            //放入最后一个下标内
            elem[usedSize++] = val;//11
            shiftUp(usedSize-1);//10
    
        }
        //判断是否满（数组存储）
        public boolean isFull(){
        
    
            return usedSize == elem.length;
        }

### 3.堆的删除 ###

#### 3.1原理 ####

1.观察可知，堆删除最后一个节点时只需要usedSize–即可，（也是定义usedSize的好处），所以我们可以将第一个结点的值与最后一个节点的值交换，然后再将第一个节点向下调整，即可。

2.时间复杂度：即树的高度O(logN)

#### 3.2 代码 ####

/*
        堆的删除
        交换第一个值和最后一个的值，usedSie--即删除
         */
        public void pop(){
        
            if(!isEmpty()){
        
               swap(elem,0,usedSize-1);
               usedSize--;
               shiftDown(0,usedSize);
            }else {
        
                return;
            }
    
        }
        //判断是否为空
        public boolean isEmpty(){
        
            return usedSize == 0;
        }
        public void swap(int[]elem,int i,int j){
        
            int temp = elem[i];
            elem[i] = elem[j];
            elem[j] = temp;
    
        }

### 4.获取堆顶元素 ###

由于数组存储，只需要返回数组第一个值即可

//获取堆顶元素
        public int peekHeap(){
        
            return elem[0];
        }

[Link 1]: http://t.csdn.cn/finiG