二叉堆的建立、插入、删除

一、基本概念：

1、完全二叉树：若二叉树的深度为h，则除第h层外，其他层的结点全部达到最大值，且第h层的所有结点都集中在左子树。

2、满二叉树：满二叉树是一种特殊的的完全二叉树，所有层的结点都是最大值。

二叉堆

二叉堆是基于完全二叉树的基础上，加以一定的条件约束的一种特殊的二叉树。

根据约束条件的不同，二叉堆又可以分为两个类型：

大顶堆和小顶堆。

大顶堆

即任何一个父节点的值，都 大于等于 它左右孩子节点的值。

小顶堆

即任何一个父节点的值，都 小于等于 它左右孩子节点的值。 二叉堆的根节点叫做 堆顶 ，它是大顶堆里面的最大值，小顶堆里的最小值。

二、 构造最大堆

原始数据为a = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7}，采用顺序存储方式，对应的完全二叉树如下图所示：

1、基本思想

首先将每个叶子节点视为一个堆，再将每个叶子节点与其父节点一起构造成一个包含更多节点的堆。所以，在构造堆的时候，首先需要找到最后一个节点的父节点，从这个节点开始构造最大堆；直到该节点前面所有分支节点都处理完毕，这样最大堆就构造完毕了。

假设树的节点个数为n，以1为下标开始编号，直到n结束。对于节点i，其父节点为i/2；左孩子节点为i2，右孩子节点为i*2+1。最后一个节点的下标为n，其父节点的下标为n/2。

我们边针对上边数组操作如下图所示，最后一个节点为7，其父节点为16，从16这个节点开始构造最大堆；构造完毕之后，转移到下一个父节点2，直到所有父节点都构造完毕。

2、代码实现

因为堆是基于完全二叉树，所以我们不需要用链式结构来表示，我们可以直接用数组存。

假设父节点的下表为parent，从父节点获取子节点：

左节点下标： 2parent+1*

右节点下标： 2parent+2*

假设子节点的下标为son(左右子节点都可以)：

父节点下标：(son-1)/2

所以我们可以非常简单的表示出节点之间的关系了，下面是代码：

public class MaxHeap {
    // 数据元素个数
    private int heapSize;
    // 存放元素的空间大小
    private int maxSize;
    // 数据元素的存放
    Integer[] data;
    
    public MaxHeap(Integer[] pData,int maxSize) {
        this.maxSize = maxSize;
        data = new Integer[maxSize];
        for (int i = 0; i < pData.length; i++) {
            data[i] =pData[i];
        }
        this.heapSize = pData.length;
        // 初始化最大堆
        initMapHeap(heapSize -1);
    }
    //获取左节点
    private int getLeft(int parent)
    {
        return 2 * parent + 1;
    }
    //获取右节点
    private int getRight(int parent)
    {
        return 2 * parent + 2;
    }
    private int getParent(int son) //获取父节点
    {
        if (son <= 0) {
            return -1;
        }
        return (son - 1) / 2;
    }
    
    private void initMapHeap(int index) {
        while (index > 0 ) {
            int parentIndex = getParent(index);
            // 当前父节点，有右节点和左节点
            if (getRight(parentIndex) < heapSize) {
                Integer leftData = data[getLeft(parentIndex)];
                Integer rightData = data[getRight(parentIndex)];
                Integer ParentData = data[parentIndex];
                // 左边节点 > 右边节点
                if (leftData >= rightData) {
                    // 左边节点，还大于 父节点
                    if (leftData > ParentData) {
                        // 左节点和父节点，交换数据
                        data[parentIndex] = leftData;
                        data[getLeft(parentIndex)] = ParentData;
                        // 每次比较完成后，后面的节点还要进行比较，直接都进行重新比较
                        index = heapSize -1;
                    }
                } else {
                    // 右边节点，> 左边节点，> 父节点点
                    if (rightData > ParentData ) {
                        // 右节点和父节点交换数据
                        data[parentIndex] = rightData;
                        data[getRight(parentIndex)] = ParentData;
                        // 每次比较完成后，后面的节点还要进行比较，直接都进行重新比较
                        index = heapSize -1;
                    }
                }
            } else {
                // 只有左节点
                Integer leftData = data[getLeft(parentIndex)];
                Integer ParentData = data[parentIndex];
                // 左边节点，还大于 父节点
                if (leftData > ParentData) {
                    // 左节点和父节点，交换数据
                    data[parentIndex] = leftData;
                    data[getLeft(parentIndex)] = ParentData;
                    index = heapSize -1;
                }
            }
            index--;
        }
    }
    
    public int getHeapSize() {
        return heapSize;
    }
    
    public Integer[] getData() {
        Integer[] integer = new Integer[heapSize];
        for (int i = 0; i < heapSize; i++) {
            integer[i] = data[i];
        }
        return integer;
    }
}

三、 插入节点

最大堆的插入节点的思想就是先在堆的最后添加一个节点，然后沿着堆树上升。跟最大堆的初始化过程大致相同。

public void insertData(Integer num) {
    heapSize++;
    data[heapSize-1] = num;
    initMapHeap(heapSize -1);
}

四、顶节点删除

最大堆堆顶节点删除思想如下：将堆树的最后的节点提到根结点，然后删除最大值，然后再把新的根节点放到合适的位置。

public void del(Integer num) {
   // 找到要删除元素的索引
    int i = 0;
    for (; i < heapSize; i++) {
        if (data[i].intValue()  == num.intValue()) {
            break;
        }
    }
    // 删除索引处值，
    for(int j = i ;j < heapSize -1;j++) {
        data[j] = data[j+1];
    }
    // 最后一个值，置空
    data[heapSize -1] = null;
    // 大小-1
    heapSize--;
    // 重新初始化
    initMapHeap(heapSize -1);
}