Java數據結構中的堆怎么應用

本篇內容介紹了“Java數據結構中的堆怎么應用”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！

一、堆的創建

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、優先級隊列的構造

“Java數據結構中的堆怎么應用”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！