堆：是用数组实现的完全二叉树，没有使用指针，根据数组的下标进行构建堆
eg：parentIndex = i;—》 leftIndex = 2i+1;rightIndex = 2i+2;
堆的分类：大根堆，小根堆。大根堆的每个子树，根节点是整个树中最大的数据，每个节点的数据都比其子节点大
小根堆的根节点数据是最小的数据，每个节点的数据都比其子节点小

注意：堆的根节点中存放的是最大或者最小元素，但是其他节点的排序顺序是未知的。例如，在一个最大堆中，最大的那一个元素总是位于 index 0 的位置，但是最小的元素则未必是最后一个元素。–唯一能够保证的是最小的元素是一个叶节点，但是不确定是哪一个。
（以小根堆为例 讲解 堆的构建，插入和删除过程）
一，堆的构建
从末尾节点的父节点的这棵树开始调整，根据小根堆的性质，越小的数据往上移动，注意，被调整的节点还有子节点的情况，需要递归进行调整。

2和3交换之后，3所处的节点还有子节点，需要递归检验3所在树是否也符合小根堆的性质

注意：此时9和1发生交换之后，9所处的节点具有子节点，递归调整9所处的树

至此，小根堆构建的过程就完成了，下面看下代码层面的实现

private List<Integer> arr;
/**
     * 构建最小堆，从最后一个节点的父节点开始调整（也可以对数组中某段连续数据即下标从firstIndex -> endIndex进行建堆）
     * @param firstIndex 起始下标
     * @param enIndex    结束下标
     */
public void buildMinHeap(int firstIndex,int enIndex) {
        for (int i = enIndex/2; i >= firstIndex; i--) {
            adjustDown(i,enIndex);
        }
    }
    /**
     * 调整当前子树，越小的数据往上移动，注意调整的该节点还有子节点的情况，所以需要递归调整。
     * @param parentIndex  父节点的下标
     */
    private void adjustDown(int parentIndex,int endIndex) {
        int left = 2 * parentIndex + 1;
        int right = 2 * parentIndex + 2;
        //最小值的下标
        int minIndex = parentIndex;
        if (left < endIndex && arr.get(left) < arr.get(minIndex)) {
            minIndex = left;
        }
        if (right < endIndex && arr.get(right) < arr.get(minIndex)) {
            minIndex = right;
        }
        if(minIndex == parentIndex){
            return;
        }
        //交换元素
        swap(parentIndex,minIndex);
        //递归调整
        adjustDown(minIndex,endIndex);
    }
    private void swap(int parentIndex,int minIndex){
        int temp = arr.get(parentIndex);
        arr.set(parentIndex,arr.get(minIndex));
        arr.set(minIndex,temp);
    }

二、插入
新增元素首先插入在堆的末尾元素，然后依据小根堆的性质，自底向上，递归调整。
以上面构建的小根堆为例，新插入元素0。
1，首先在堆的末尾插入新增元素

2，自底向上，递归调整其父节点



（插入是在小根堆构建完成的基础上进行的操作，所以在交换之后其子节点所在的树也都是小根堆，所以不需要再进行递归调整）
代码实现：

/**
     * @param item 要插入的元素
     */
    public void insertToMinHeap(int item){
        arr.add(item);
        //根节点
        if(arr.size() == 1){
            return;
        }
        adjustUp(arr.size()-1);

    }

    /**
     * 向上调整
     * @param childIndex 要往上调整的子节点的下标
     */
    private void adjustUp(int childIndex){
        int parentIndex = (childIndex - 1)/2;
        int parentItem = arr.get(parentIndex);
        int childItem = arr.get(childIndex);

        if(parentItem > childItem){
            swap(parentIndex,childIndex);
            adjustUp(parentIndex);
        }
    }

三、堆删除
对于最大堆和最小堆，删除操作是针对堆顶元素而言的，即把末尾元素移动到堆顶，再自定向下(重复构建堆的操作)，递归调整。
1，将末尾元素移动到堆顶




此时所有的子树都符合小根堆的性质了，即完成堆调整。
代码实现：

 public int deleteMinHeap(){
        //取出最小元素，并将最后一个元素置顶
        int minItem = arr.get(0);
        arr.set(0,arr.get(arr.size()-1));
        //移除末尾元素
        if(arr.size() > 1){
            arr.remove(arr.size() - 1);
        }
        //向下调整堆(该实现见上面)
        adjustDown(0,arr.size()-1);
        return minItem;
    }

四、堆排序：（升序–》大根堆，降序–》小根堆）
利用大根堆/小根堆的特性（以小根堆为例），第一次建完小根堆之后，最小的元素将位于0号下标，将0号元素和最后一个元素交换，然后再将剩下的树再建小根堆，循环进行此操作直到完成所有数据
1，将无序数组构建成小根堆

2，将堆顶元素和末尾元素交换位置，使最小元素落在末尾

3，除了2步骤落到末尾的元素，对剩下的元素继续建小根堆(重复1，2的动作)，直到完成所有的元素即完成排序

代码实现：

/**
     * 先建成最小堆，再将堆顶元素和堆尾元素交换，除了当前堆的堆尾元素，对剩下的元素再次进行建堆
     */
    public void heapSort(){
        for(int i = 0;i<arr.size();i++){
            buildMinHeap(0,arr.size()-1-i);
            swap(0,arr.size()-1-i);
        }
    }

五，堆和二叉排序树的区别
内存占用：二叉排序树占用的内存空间比我们存储的数据要多，需要分配额外的内存来存储指针指向其左右子节点。堆的实现结构是数据，根据数组具有下标这一特性来执行左/右子节点。
节点的顺序：在二叉排序树中，左子节点必须比父节点小，右子节点必须比父节点大。但是在堆中并非如痴，在小根堆中两个子节点都必须比父节点小，并且左右子节点的数据大小是不确定的。
搜索性能：二叉排序树是为了实现动态查找而涉及的数据结构，它是面向查找操作的，在二叉排序树中查找一个节点的平均时间复杂度是O(logn)；在堆中搜索并不是第一优先级，堆是为了实现排序而实现的一种数据结构，它不是面向查找操作的，因为在堆中查找一个节点需要进行遍历，其平均时间复杂度是O(n)。