一、二叉树的顺序存储

使用数组保存二叉树结构，方式，即将二叉树用层序遍历的方式放入数组中。一般只适合表示完全二叉树，因为非完全二叉树会有空间的浪费。这种方式的主要用法就是堆的表示。

堆主要用到已知父节点，判断子节点位置，父节点和子节点下标关系：
已知父节点下标i，左孩子下标2i+1；右孩子下标2i+2；
已知孩子（不区分左右）下标j，父节点下标(j-1)/2；

二、堆的概念和创建

1、什么是堆？

堆逻辑上是一棵完全二叉树，物理上是保存在数组中，满足任意节点的值都大于其子树中节点的值，叫做大堆，或者大根堆，或者最大堆，反之，则是最小堆或者小根堆，或者最小堆。堆的基本作用是快速找集合中的最值

示例：pandas 是基于NumPy 的一种工具，该工具是为了解决数据分析任务而创建的。

2、向下调整和创建堆

前提：左右子树必须已经是一个堆，才能调整

//向上调整
    public void adjustDown(int parent,int len){
        int child = 2*parent+1;
        while(child < len){
            if(child+1 < len&&this.elem[child] < this.elem[child+1]){//有右节点
                child++;//用child 表示左右子节点中较大的数的下标
            }
            if(this.elem[parent] < this.elem[child]){
                int tmp = this.elem[parent];
                this.elem[parent] = this.elem[child];
                this.elem[child] = tmp;
                parent = child;
                child = 2*parent+1;
            }
        }
    }

    //创建大根堆
    public void createHeap(int[] array){
        for (int i = 0; i < array.length; i++) {
            this.elem[i] = array[i];
            useSize++;
        }
        for(int p = (array.length-1-1)/2;p >= 0;p--){
            adjustDown(p,useSize);
        }
    }

三、堆应用

1、操作——入队列

1.首先按尾插方式放入数组
2. 比较其和其双亲的值的大小，如果双亲的值大，则满足堆的性质，插入结束
3. 否则，交换其和双亲位置的值，重新进行 2、3 步骤
4. 直到根结点

//入队列   尾插到数组后
public void adjustUp(int[] array,int child){
        for (int i = 0; i < array.length; i++) {
            this.elem[i] = array[i];
            useSize++;
        }
        while(child > 0){
            int parent = (child-1)/2;
            if(this.elem[parent] > this.elem[child])break;
            int tmp = this.elem[parent];
            this.elem[parent] = this.elem[child];
            this.elem[child] = tmp;

            child = parent;//原本已经是大根堆，现在只要判断父子节点即可
        }
    }

2、操作——出队列

为了防止破坏堆的结构，删除时并不是直接将堆顶元素删除，而是用数组的最后一个元素替换堆顶元素，然后通过向下调整方式重新调整成堆。

//出队列    （已经是一个大根堆或小根堆,假设大根堆）用数组最后一个元素替换栈顶元素，然后向上调整（不用管替换后的最后一个元素）
public int outTreeNode(){
        int tmp = this.elem[useSize-1];
        this.elem[useSize-1] = this.elem[0];
        this.elem[0] = tmp;
        this.useSize--;
        int parent = 0;
        adjustDown(parent,useSize-1);
        return this.elem[useSize];
    }

3、java中的优先级队列

PriorityQueue可以创建堆，默认为小堆

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
            //接口不能被实例化，后面加花括号,表示一个类实现了这个接口，这个类是匿名内部类
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;//最小堆
                //return o2 - o1;//最大堆
            }
        });

4、堆的其他应用—TopK问题

提示：找前k个最大，要建k个大小的小堆
步骤：
1.建立大小为k的小堆
2.遍历数组，将前k个数放入小堆
3.从k+1个元素开始，和堆顶元素进行比较
4.输出堆里的元素

//求前K个最大的    topK问题
    public void topK(int[] arr,int k){
        //建立大小为k的小堆          o2 - o1为大堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k,new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });
        //遍历数组，将前k个数放入小堆
        for (int i = 0; i < k; i++) {
            minHeap.offer(arr[i]);
        }
        //从k+1个元素开始，和堆顶元素进行比较
        for(int i = k + 1;i < arr.length;i++){
            //当前元素比堆顶大，先出后入
            Integer val = minHeap.peek();
            if(arr[i] > val){
                minHeap.poll();
                minHeap.offer(arr[i]);
            }
        }
        //输入堆里的元素
        System.out.println(minHeap);
    }