Java篇—“堆”详解（初始化，插入堆，删除堆顶元素，堆排序）

迷南。 2021-11-27 05:42 355阅读 0赞

**堆：**

（1）堆通常是一个可以被看做一棵树的数组对象。

（2）将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

（3）堆是非线性数据结构，相当于一维数组，有两个直接后继。

**堆的定义：**

（1）n个元素的序列\{k1,k2,ki,…,kn\}当且仅当满足下关系时，称之为堆。

(ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4...n/2)

上述可以理解为，父节点小于等于孩子节点（小根堆），父节点大于等于孩子节点（大根堆）

（2）若将和此次序列对应的一维数组（即以一维数组作此序列的存储结构）看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值。由此，若序列\{k1,k2,…,kn\}是堆，则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）。

**堆的性质：**

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

（2）堆总是一棵完全二叉树。

**完全二叉树抽象图：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc2MTY1OQ_size_16_color_FFFFFF_t_70][]

**接口定义：**

public interface IHeap {
        从每颗子树的根节点开始调整 调整的长度为len
        void AdjustDown(int root,int len);
        //初始化建立大根堆
        public void initHeap(int[] array);
        //向上调整，从孩子节点开始调整
        void AdjustUp(int child);
        // 插入 item 到堆中
        void pushHeap(int item);
        // 返回堆顶元素，删除数据元素
        int popHeap();
        // 返回堆顶元素，不删除数据元素
        int getHeapTop();
        //堆排序
        void HeapSort();
        //打印堆
        void show();
    }

**详细代码及注释：**

package com.jia.impl;
    import com.jia.dao.IHeap;
    import java.util.Arrays;
    public class TestHeap implements IHeap {
        //接收堆（将堆看为一维数组）
        private int[] elem;
        //数据个数
        private int usedSize;
        //定义堆的容量
        private final int DEFAULT_SIZE = 10;
        public TestHeap(){
            this.elem = new int[DEFAULT_SIZE];
            this.usedSize = 0;
        }
        //从每颗子树的根节点开始调整 调整的长度为len
        @Override
        public void AdjustDown(int root, int len) {
            int parent = root;
            //左孩子
            int child = 2*parent + 1;
            while(child < len){
                //判断有没有右孩子
                if(child + 1 < len && this.elem[child] < this.elem[child+1]){
                    child++;
                }
                //此时child为最大值的下标
                //判断子节点和父节点，如果孩子节点大于父节点，交换数值
                if(this.elem[child] > this.elem[parent]){
                    int temp = this.elem[child];
                    this.elem[child] = this.elem[parent];
                    this.elem[parent] = temp;
                    //交换完毕后，孩子节点也能有它的孩子节点
                    parent = child;
                    child = 2*parent + 1;
                }else{
                    //子节点不大于父节点，跳出循环即可
                    break;
                }
            }
    
        }
    
        //初始化建立大根堆
        @Override
        public void initHeap(int[] array) {
            //用elem[] 来 接收 array[]
            for (int i = 0; i < array.length; i++) {
                this.elem[i] = array[i];
                this.usedSize++;
            }
            //开始调整堆，每一颗子树都需要调整,子推父——（n-1）/2    n:孩子的下标
            for (int i = (elem.length - 1 - 1)/2; i >= 0 ; i--) {
                AdjustDown(i,usedSize);
            }
        }
        //向上调整，从孩子节点开始调整
        @Override
        public void AdjustUp(int child) {
            int parent = (child - 1)/2;
            while(child > 0){
                //孩子节点大于父节点，交换
                if(this.elem[child] > this.elem[parent]){
                    int temp = this.elem[child];
                    this.elem[child] = this.elem[parent];
                    this.elem[parent] = temp;
                    //前面已经将堆构建为大根堆
                    //父节点和它的父节点也要比较
                    child = parent;
                    parent = (child - 1)/2;
                }else{
                    //如果不大于，跳出循环即可
                    break;
                }
            }
        }
        // 插入 item 到堆中
        @Override
        public void pushHeap(int item) {
            //先判断数组的容量是否已达最大值
            if(isFull()){
                //数组扩容
                this.elem = Arrays.copyOf(this.elem,this.elem.length*2);
            }
            this.elem[this.usedSize] = item;
            usedSize++;
            //插入数据后重新进行大根堆的建立，此时只需要向上调整即可
            AdjustUp(this.usedSize - 1);
        }
    
        private boolean isFull() {
            if(this.usedSize == this.elem.length){
                return true;
            }
            return false;
        }
    
        // 返回堆顶元素，删除数据元素
        @Override
        public int popHeap() {
            //判断堆是否为空
            if(this.usedSize == 0){
                throw new UnsupportedOperationException("堆为空，无法删除！");
            }
            //删除分析：让堆顶元素和最后一个孩子节点交换，usedSize-1,即可
            int temp = this.elem[0];
            this.elem[0] = this.elem[this.usedSize - 1];
            this.elem[this.usedSize - 1] = temp;
            this.usedSize--;
            //删除后，重新构建大根堆，向下调整
            AdjustDown(0,this.usedSize);
            return this.elem[0];
        }
        // 返回堆顶元素，不删除数据元素
        @Override
        public int getHeapTop() {
            //判断堆是否为空
            if(this.usedSize == 0){
                throw new UnsupportedOperationException("堆为空，无法删除！");
            }
            return this.elem[0];
        }
        //堆排序
        @Override
        public void HeapSort() {
            int end = this.usedSize - 1;
            while(end > 0){
                int temp = this.elem[0];
                this.elem[0] = this.elem[end];
                this.elem[end] = temp;
                end--;
            }
        }
        //打印堆
        @Override
        public void show() {
            for (int i = 0; i < usedSize; i++) {
                System.out.print(this.elem[i]+" ");
            }
            System.out.println();
        }
    }

**题目总结：**不理解就画图！很多你看着简单的知识点，没有亲手练习过，都是空谈！数据结构，个人理解，画图很重要。

**心灵鸡汤：梦想很近，咫尺之间，遥不可及只是你未曾努力！**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc2MTY1OQ_size_16_color_FFFFFF_t_70]: /images/20211126/988584ec936c46f3856033b285d87514.png