堆(Heap or PriorityQueue) Java

認識堆（優先級佇列）

1.堆又叫優先級佇列，邏輯上上是一棵完全二叉樹，堆物理上基于陣列實作
2.堆可分為大堆（大根堆、最大堆）和小堆（小根堆、最小堆）

堆（優先級佇列）操作方法

public class MyHeap {

    private int[] elem;
    private int usedSzie;

    public MyHeap(int k){
        this.elem = new int[k];
    }

    //創建大堆
    public void createBigHeap(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            this.elem[i] = arr[i];
            this.usedSzie++;
        }
        //i表示父親結點，依次調整
        for (int i = (this.usedSzie-2)/2; i >= 0 ; i--) {
            adjustDown(i, this.usedSzie);
        }
    }

    //向下調整
    public void adjustDown(int parent, int len){
        int child = 2*parent+1;
        //len代表陣列實際長度
        //child小于len說明 parent有左孩子，不能確定是否有右孩子 child==len說明 parent沒有左右孩子
        while(child < len){
            //child+1 < len保證當前父親結點有右孩子
            //當左孩子小于右孩子時，child走到右孩子下標，保證child是左右孩子最大值下標
            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*parent+1;
            }else{
                //我們是從最后一棵樹調整的
                //當this.elem[child] <= this.elem[parent]時,表明此時的樹是大根堆，后面不需要回圈了
                break;
            }
        }
    }

    //創建小堆
    public void createSmallHeap(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            this.elem[i] = arr[i];
            this.usedSzie++;
        }
        //i表示父親結點，依次調整
        for (int i = (this.usedSzie-2)/2; i >= 0 ; i--) {
            adjustDown1(i, this.usedSzie);
        }
    }

    //向下調整
    public void adjustDown1(int parent, int len){
        int child = 2*parent+1;
        //len代表陣列實際長度
        //child小于len說明 parent有左孩子，不能確定是否有右孩子 child==len說明 parent沒有左右孩子
        while(child < len){
            //child+1 < len保證當前父親結點有右孩子
            //當左孩子小于右孩子時，child走到右孩子下標，保證child是左右孩子最大值下標
            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*parent+1;
            }else{
                //我們是從最后一棵樹調整的
                //當this.elem[?child] <= this.elem[parent]時,表明此時的樹是大根堆，后面不需要回圈了
                break;
            }
        }
    }


    //向上調整
    //這里的child第一次就是入隊元素的下標，
    public void adjustUp(int child){
        int parent = (child-1)/2;
        //child等于0相當于已經調整了位置，此時parent為負數了
        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 val){
        if(isFull()){
            this.elem = Arrays.copyOf(this.elem, this.elem.length*2);
        }
        this.elem[usedSzie] = val;
        this.usedSzie++; //例如元素為10，此時useDsize為11
        adjustUp(usedSzie-1);
    }

    //元素出優先級佇列
    //思想：隊頭和隊尾交換 向下調整0下標這棵樹
    public int poll(){
        if(isEmpty()) {
            throw new RuntimeException("佇列為空");
        }
        int ret = this.elem[0]; //保存隊頭元素
        int tmp = this.elem[0];
        this.elem[0] = this.elem[usedSzie];
        this.elem[usedSzie] = tmp;
        //相當于原來的隊頭元素被拿走了
        this.usedSzie--;  /
        adjustDown(0,usedSzie);
        return ret;
    }

    //拿到隊頭元素不洗掉
    public int peek(){
        if(isEmpty()) {
            throw new RuntimeException("佇列為空");
        }
        return this.elem[0];
    }


    //優先級佇列用堆創建，而堆基于陣列，當陣列已滿時，需要擴容
    public boolean isFull(){
        return this.usedSzie == this.elem.length;
    }

    //判空
    public boolean isEmpty(){
        return this.usedSzie == 0;
    }

    public void display(){
        for (int i = 0; i < this.usedSzie; i++) {
            if(i == 0) {
                System.out.print("["+this.elem[i]+" ");
            }else if(i == usedSzie-1){
                System.out.print(this.elem[i]+"]");
            }else{
                System.out.print(this.elem[i]+" ");
            }
        }
    }


}

主函式測驗用例

public class TestDemo {
    public static void main(String[] args) {
        MyHeap heap = new MyHeap(10);
        int[] array = {27,15,19,18,28,34,65,49,25,37};
        System.out.println("原來的堆: "+Arrays.toString(array));
        heap.createBigHeap(array);
        System.out.print("現在的大根堆: ");
        heap.display();
        System.out.println();
        heap.push(200);
        heap.display();
        System.out.println(heap.poll());
        heap.display();
    }
}