数据结构-树-堆-基础

堆是一种特殊的树，那么堆有什么样的特点呢？

1. 堆是一颗完全二叉树
2. 堆必须满足其任意节点都要大于等于（或小于等于）其左右子节点（大于等于还是小于等于取决于要构建一个大顶堆还是小顶堆

堆的实现

因为堆是一颗完全二叉树，我们知道完全二叉树是很适合用数组存储的（因为不会有空间浪费）

堆的插入

简单的插入动作会破坏堆的特性，所以我们要在数据插入后，重新根据堆的特性重新调整数组使其重新符合堆的特性，这个过程叫做堆化。
堆化分为自上而下和自下而上，插入一般是自下而上的堆化过程。
以大顶堆为例子，插入的逻辑其实就是在堆的最后（其实就是数组里的第一个空的位置）插入一个元素，然后不停的和父节点比较，如果插入数据大于父节点，则和父节点交换，直到无法交换为止

堆的插入

package tree;

/**
 * @author TioSun
 */

public class Heap {
    /**
     * 数组，从下标1开始存储数据
     */
    private int[] a;
    /**
     * 堆可以存储的最大数据个数
     */
    private int capacity;
    /**
     * 堆中已经存在的数据个数
     */
    private int count;

    public Heap(int capacity) {
        this.a = new int[capacity + 1];
        this.capacity = capacity;
        this.count = 0;
    }

    public void insert(int data) {
        // 判断是否堆满
        if (count >= capacity) {
            return;
        }
        ++count;
        a[count] = data;
        // 表示新插入数据的当前位置
        int i = count;
        // 自下而上堆化
        while (i/2 > 0 && a[i] > a[i/2]) {
            int temp = a[i];
            a[i] = a[i/2];
            a[i/2] = temp;
            i = i/2;
        }
    }
}

删除堆顶元素

删除堆顶元素的一般做法是用最后一个元素去替换堆顶元素，然后自上而下堆化。
以大顶堆为例，自上而下堆化的步骤是将堆顶元素和左右子节点进行比较，如果小于左右子节点中的其中一个节点，则交换，如果小于左右两个子节点，则和左右子节点中的大的那个交换，重复该步骤，直到无法交换
参照下图，删除堆顶元素41的步骤如下

1. 将堆顶元素41用29替换
2. 将29和27、39比较
3. 29和39交换
4. 29和33、36比较
5. 29和36交换

6. 29和26比较，无法交换，堆化结束

   
   大顶堆

package tree;

/**
 * @author TioSun
 */

public class Heap {
    /**
     * 数组，从下标1开始存储数据
     */
    private int[] a;
    /**
     * 堆可以存储的最大数据个数
     */
    private int capacity;
    /**
     * 堆中已经存在的数据个数
     */
    private int count;

    public Heap(int capacity) {
        this.a = new int[capacity + 1];
        this.capacity = capacity;
        this.count = 0;
    }

    public void removeTop() {

        if (count == 0) {
            return;
        }
        // 将堆顶元素用最后一个元素替换
        a[1] = a[count];
        count--;
        // 表示替换后的数据的当前位置
        int i = 1;
        while (true) {
            // 需要交换的目标位置，先设为当前位置以表示无需交换
            int targetIndex = i;
            // 尝试和左子节点比较
            if (i * 2 < count && a[i] < a[i * 2]) {
                // 将交换位置暂定为左子节点
                targetIndex = i * 2;
            }
            // 尝试和右子节点比较
            if (i * 2 + 1 < count && a[targetIndex] < a[i * 2 + 1]) {
                targetIndex = i * 2 + 1;
            }
            if (targetIndex == i) {
                // 无需交换
                break;
            }
            // 与待交换位置的元素交换
            int temp = a[i];
            a[i] = a[targetIndex];
            a[targetIndex] = temp;
            
            i = targetIndex;

        }
    }
}