Java 超詳細講解資料結構中的堆的應用

2022-04-01 22:00:14

一、堆的建立

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

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

如果parent的左孩子存在，即:child < size，進行以下操作，直到parent的左孩子不存在：

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) :

(oldCapacity >> 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 超詳細講解資料結構中的堆的應用的文章就介紹到這了,更多相關Java 堆的應用內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！