Java堆的應用場景與實作方法介紹

一、堆的創建

1、向下調整（以小堆為例）  

讓parent標記需要調整的節點，child標記parent的左孩子(注意：parent如果有孩子一定先是有左孩子)

如果parent的左孩子存在，即:child

• parent右孩子是否存在，存在找到左右孩子中最小的孩子，讓child進行標記

• #將parent與較小的孩子child比較，如果：

parent小於較小的孩子child，調整結束否則：交換parent與較小的孩子child，交換完成之後，parent中大的元素向下移動，可能導致子樹不滿足堆的性質，因此需要繼續向下調整，即parent = child；child = parent*2 1; 然後繼續2。

public void shiftDown(int[] elem,int parent,int len){
        int cur=parent*2+1;
        while(cur<len){
           if(cur+1<len){
               if(elem[cur+1]<elem[cur]){
                   cur++;
               }
           }
            if(this.elem[cur]<this.elem[parent]) {
                swap(cur, parent);
            }
            parent=cur;
            cur=parent*2+1;
        }
    }

2、建立堆疊

對於普通序列，我們需要從它的第一個有左節點的父節點開始調整，知道整棵樹滿足堆的性質。

3、創建堆的時間複雜度

堆必須是完全二元樹，滿二叉樹也是完全二元樹。由下面的計算，創建堆的時間複雜度為O(n).

# 二、堆的插入和刪除

1、堆的插入

• 將要插入的元素放在堆的最後，如果放不了，進行擴容

• 將新插入的節點向上調整，直到滿足堆的性質

 【向上調整】

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

2、堆的刪除

根據堆的性質，對刪除的一定是堆頂元素。步驟如下：

• 將堆頂元素與最後一個元素交換

• 堆的元素數量減一

• 對堆頂元素進行向下調整

# 三、堆的應用

1、堆排序

升序：建立大根堆

降序：建立小根堆

交換堆頂元素和堆得最後一個元素，進行向下調整，直到堆有序。

2、top-k問題 【求最小的K個數】

top-k問題：求資料集合中前k個大或小的元素，一般資料量都比較大。

class Solution {
    public int[] smallestK(int[] arr, int k) {
        int[] array=new int[k];
        if(arr==null||arr.length<=k||k==0){
            return array;
        }
        PriorityQueue<Integer> queue=new PriorityQueue<>((a,b)->b-a);
        int i=0;
        for(;i<k;++i){
            queue.offer(arr[i]);
        }
        while(i<arr.length){
            if(arr[i]<queue.peek()){
                queue.poll();
                queue.offer(arr[i]);
            }
            i++;
        }
        int size=queue.size();
        for(int j=0;j<size;++j){
            array[j]=queue.poll();
        }
        return array;
    }
}

四、常用介面的介紹

1、PriorityQueue的特性

Java集合框架中提供了PriorityQueue和PriorityBlockingQueue兩種類型的優先權隊列。 PriorityQueue是線程不安全的，PriorityBlockingQueue是線程安全的，本文主要介紹PriorityQueue。

【PriorityQueue】使用的注意事項：

• #必須匯入PeioriryQueue的套件；

• ##放置的元素必須是能夠比較大小的，否則會拋出ClassCastException異常；

• 不能放置null元素，否則會拋出NullPointerException；

• 可以插入任意多的元素，內部會自動擴容；

• 底層使用了堆疊資料結構，預設是小堆。如果要建造大堆，則需要提供比較器。

PriorityQueue的擴容方式：

• #如果容量小於64時，是依照oldCapacity的2倍方式擴容的

• 如果容量大於等於64，是依照oldCapacity的1.5倍方式擴容的

• 如果容量超過MAX_ARRAY_SIZE，依照MAX_ARRAY_SIZE來進行擴容

int newCapacity = oldCapacity ((oldCapacity < 64) ?

                      (oldCapacity 2) :           >> 1));

PriorityQueue採用了：Comparble和Comparator兩種方式。

1. Comparble是預設的內部比較方式，如果使用者插入自訂類型物件時，該類別物件必須要實作Comparble接口，並覆寫compareTo方法

2. 使用者也可以選擇使用比較器對象，如果使用者插入自訂類型物件時，必須要提供一個比較器類，讓該類別實作Comparator介面並覆寫compare方法

// 用户自己定义的比较器：直接实现Comparator接口，然后重写该接口中的compare方法即可
class IntCmp implements Comparator<Integer>{
   @Override
   public int compare(Integer o1, Integer o2) {
      return o2-o1;
   }
}
PriorityQueue<Integer> p = new PriorityQueue<>(new IntCmp());

2、优先级队列的构造

构造器	功能介绍
PriorityQueue()	创建一个空的优先级队列，默认容量是11
PriorityQueue(int initialCapacity)	创建一个初始容量为initialCapacity的优先级队列，注意： initialCapacity不能小于1，否则会抛IllegalArgumentException异 常
PriorityQueue(Collection extends E> c)	用一个集合来创建优先级队列

以上是Java堆的應用場景與實作方法介紹的詳細內容。更多資訊請關注PHP中文網其他相關文章！