Java資料結構之堆怎麼建立

堆的性質

堆邏輯上是一棵完全二元樹，堆物理上是保存在陣列中 。

總結：一顆完全二元樹以層序遍歷方式放入數組中存儲，這種方式的主要用法就是堆的表示。

且如果已知父親(parent) 的下標，

則： 左孩子(left) 下標= 2 * parent 1;

右孩子(right)下標= 2 * parent 2;

已知孩子（不區分左右）(child)下標，則：

雙親(parent) 下標= (child - 1) / 2 ;

堆的分類

大堆：根節點大於左右兩個子節點的完全二元樹（父親節點大於其子節點），叫做大堆，或大根堆，或最大堆。

小堆：根節點小於左右兩個子節點的完全二元樹叫 小堆（父親節點小於其子節點），或小根堆，或最小堆。

堆的向下調整

現在有一個數組，邏輯上是完全二元樹，我們透過從根節點開始的向下調整演算法可以把它調整成一個小堆或大堆。向下調整演算法有一個前提：左右子樹必須是一個堆，才能調整。

以小堆為例：

1、先讓左右孩子結點比較，取最小值。

2、用較小的那個孩子結點與父親節點比較，如果孩子結點

3、循環往復，如果孩子結點的下標越界，則表示已經到了最後，就結束。

程式碼範例：

 //parent: 每棵树的根节点
 //len: 每棵树的调整的结束位置
public void shiftDown(int parent,int len){
        int child=parent*2+1; //因为堆是完全二叉树，没有左孩子就一定没有右孩子，所以最起码是有左孩子的，至少有1个孩子
        while(child<len){
            if(child+1<len && elem[child]<elem[child+1]){
                child++;//两孩子结点比较取较小值
            }
            if(elem[child]<elem[parent]){
                int tmp=elem[parent];
                elem[parent]=elem[child];
                elem[child]=tmp;
                parent=child;
                child=parent*2+1;
            }else{
                break;
            }
        }
    }

堆的建立

給出一個數組，這個數組邏輯上可以看做一顆完全二叉樹，但是還不是一個堆（左右子樹不滿足都是大堆或小堆），現在我們透過演算法，把它建構成一個堆（大堆或小堆）。該怎麼做呢？這裡我們從倒數的第一個非葉子節點的子樹開始調整，一直調整到根節點的樹，就可以調整成堆。這裡我們就要用到剛才寫的向下調整。

public void creatHeap(int[] arr){
        for(int i=0;i<arr.length;i++){
            elem[i]=arr[i];
            useSize++;
        }
        for(int parent=(useSize-1-1)/2;parent>=0;parent--){//数组下标从0开始
            shiftDown(parent,useSize);
        }
    }

建堆的空間複雜度為O（N），因為堆為一棵完全二元樹，滿二叉樹也是一種完全二元樹，我們用滿二叉樹（最壞情況下）來證明。

堆得向上調整

現在有一個堆，我們需要在堆的末端插入數據，再對其進行調整，使其仍然保持堆的結構，這就是向上調整。

以大堆為例：

程式碼範例：

public void shiftup(int child){
        int parent=(child-1)/2;
        while(child>0){
            if(elem[child]>elem[parent]){
                int tmp=elem[parent];
                elem[parent]=elem[child];
                elem[child]=tmp;
                child=parent;
                parent=(child-1)/2;
            }else{
                break;
            }
        }
    }

堆的常用操作

#進入佇列

往堆裡面加入元素，就是往最後一個位置加入，然後在進行向上調整。

public boolean isFull(){
        return elem.length==useSize;
    }
public void offer(int val){
        if(isFull()){
            elem= Arrays.copyOf(elem,2*elem.length);//扩容
        }
        elem[useSize++]=val;
        shiftup(useSize-1);
    }

出佇列

把堆裡元素刪除，就把堆頂元素和最後一個元素交換，然後往整個陣列大小減一，最後往下調整，就刪除了棧頂元素。

public boolean isEmpty(){
        return useSize==0;
    }
public int poll(){
        if(isEmpty()){
            throw new RuntimeException("优先级队列为空");
        }
        int tmp=elem[0];
        elem[0]=elem[useSize-1];
        elem[useSize-1]=tmp;
        useSize--;
        shiftDown(0,useSize);
        return tmp;
    }

取得隊首元素

public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("优先级队列为空");
        }
        return elem[0];
    }

TopK 問題

給你6個數據，求前3個最大數據。這時候我們用堆怎麼做的？

解題思路：

#1、如果求前K個最大的元素，要建一個小根堆。

2、如果求前K個最小的元素,要建造一個大根堆。

3、第K大的元素。建一個小堆,堆頂元素就是第K大的元素。

4、第K小的元素。建造一個大堆,堆頂元素就是第K大的元素。

範例

舉例範例：求前n個最大資料

#程式碼範例：

 public static int[] topK(int[] array,int k){
        //创建一个大小为K的小根堆
        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<array.length;i++){
            if(minHeap.size()<k){
                minHeap.offer(array[i]);
            }else{
                //从k+1个元素开始，分别和堆顶元素比较
                int top=minHeap.peek();
                if(array[i]>top){
                    //先弹出后存入
                    minHeap.poll();
                    minHeap.offer(array[i]);
                }
            }
        }
        //将堆中元素放入数组中
        int[] tmp=new int[k];
        for(int i=0;i< tmp.length;i++){
            int top=minHeap.poll();
            tmp[i]=top;
        }
        return tmp;
    }
    public static void main(String[] args) {
        int[] array={12,8,23,6,35,22};
        int[] tmp=topK(array,3);
        System.out.println(Arrays.toString(tmp));
    }

結果：

陣列排序

再者說如果要對一個陣列進行從小到大排序，要藉助大根堆還是小根堆呢？

---->大根堆

程式碼範例：

  public void heapSort(){
        int end=useSize-1;
        while(end>0){
            int tmp=elem[0];
            elem[0]=elem[end];
            elem[end]=tmp;
            shiftDown(0,end);//假设这里向下调整为大根堆
            end--;
        }
    }

以上是Java資料結構之堆怎麼建立的詳細內容。更多資訊請關注PHP中文網其他相關文章！