数据结构之优先级队列(堆)

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

一、二叉树的顺序存储

1.存储方式

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

2.下标关系

已知双亲(parent)的下标，则：
左孩子(left)下标 = 2 * parent + 1;
右孩子(right)下标 = 2 * parent + 2;
已知孩子（不区分左右）(child)下标，则：
双亲(parent)下标 = (child - 1) / 2

二、堆

概念

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

创建大根堆

public class MyPriorityQueue {
    public int[] elem;
    public int uizSize;
    MyPriorityQueue(){
        this.elem = new int[10];
    }
    public void adjustDown(int parent , int len){
        int child = 2*parent+1;
        //用来保证child是孩子节点的最大值
        while(child < len){
            if(child+1 < len && this.elem[child] < this.elem[child+1]){
                child++;
            }
            if (this.elem[child] > this.elem[parent]){
                //交换
                int tmp = this.elem[child];
                this.elem[child] = this.elem[parent];
                this.elem[parent] = tmp;
                //交换后继续走
                parent = child;
                child = 2*child+1;
            }else{
                break;
            }
        }
    }
    //创建大根堆
    public void createHeap(int[] array){
        for (int i = 0; i < array.length; i++) {
            this.elem[i] = array[i];
            this.uizSize++;
        }
        for (int p = (this.uizSize-1-1)/2; p >= 0 ; p--) {
            //每棵树的调整方案
            adjustDown(p,this.uizSize);
        }
    }
}

建堆的时间复杂度
从代码和思想来看为O(n*log(n));
而实际上是O(n)；
建堆的过程中时间复杂度On的由来

三、堆的应用及相关操作

入队列

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

    public void adjustUp(int child){
        int parent = (child-1)/2;
        while(child > 0){
            if(this.elem[child] > this.elem[parent]){
                int tmp = this.elem[child];
                this.elem[child] = this.elem[parent];
                this.elem[parent] = tmp;
                child = parent;
                parent = (child-1)/2;
            }else{
                break;
            }
        }
    }
    //入队列
    public void push(int key){
        if(this.elem.length == this.uizSize){
            this.elem = Arrays.copyOf(this.elem,this.elem.length*2);
        }
        this.elem[this.uizSize] = key;
        this.uizSize++;
        adjustUp(this.uizSize-1);
    }

出队列

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

public void adjustDown(int parent , int len){
        int child = 2*parent+1;
        //用来保证child是孩子节点的最大值
        while(child < len){
            if(child+1 < len && this.elem[child] < this.elem[child+1]){
                child++;
            }
            if (this.elem[child] > this.elem[parent]){
                //交换
                int tmp = this.elem[child];
                this.elem[child] = this.elem[parent];
                this.elem[parent] = tmp;
                //交换后继续走
                parent = child;
                child = 2*child+1;
            }else{
                break;
            }
        }
    }
//出队列
    public int pop()throws UnsupportedClassVersionError{
        if(isEmpty()){
            throw new UnsupportedOperationException("队列为空");
        }
        int tmp = this.elem[this.uizSize-1];
        this.elem[uizSize-1] = this.elem[0];
        this.elem[0] = tmp;
        this.uizSize--;
        adjustDown(0,this.uizSize);
        return tmp;
    }
    public boolean isEmpty(){
        return this.uizSize == 0;
    }

得到队头元素

public int getTop()throws UnsupportedClassVersionError{
        if(isEmpty()){
            throw new UnsupportedOperationException("队列为空");
        }
        return this.elem[0];
    }
    public boolean isEmpty(){
        return this.uizSize == 0;
    }

四、Java中的优先级队列

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

这时就创建了一个优先级队列

细节问题

由这几行代码可知，默认创建的为一个小堆队列。

        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        priorityQueue.offer(15);
        priorityQueue.offer(60);
        priorityQueue.offer(30);
        priorityQueue.offer(25);
        System.out.println(priorityQueue.peek());

创建一个大堆队列

PriorityQueue<Integer> priorityQueue =
                new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });

使用比较器来进行创建大堆
重写了Comparator的方法

指定堆的大小来进行创建

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(10, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });

其中在创建对象时给定第一个参数为int类型，则会创建出对应大小的堆

五、Topk问题

典型问题：给定一个数值为1000的数组，来找出最大的10个数

public static void topK(int k,int array[]){
        //1.建立大小为k的小堆
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });
        //2.遍历数组元素，将前k个元素放到小堆
        for (int i = 0; i < array.length; i++) {
            if(k > 0){
                priorityQueue.offer(array[i]);
            }else {
                //3.从第k+1个值开始 和 堆顶元素比较。
                //4.当前元素比堆顶大 那么，先出pop，后入offer
                if(array[i]>priorityQueue.peek()){
                    priorityQueue.poll();
                    priorityQueue.offer(array[i]);
                }
            }
        }
        //5.输入堆里面的元素就好了
        System.out.println(priorityQueue);
    }

六、堆排序

public void heapSort(){
        int end = this.uizSize-1;
        while(end > 0){
            int tmp = this.elem[0];
            this.elem[0] = this.elem[end];
            this.elem[end] = tmp;
            adjustDown(0,end);
            end--;
        }
    }