一、堆的創(chuàng)建

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

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

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

• parent右孩子是否存在，存在找到左右孩子中最小的孩子，讓child進行標記
• 將parent與較小的孩子child比較，如果：

parent小于較小的孩子child，調整結束否則：交換parent與較小的孩子child，交換完成之后，parent中大的元素向下移動，可能導致子樹不滿足堆的性質，因此需要繼續(xù)向下調整，即parent = child；child = parent*2+1; 然后繼續(xù)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、創(chuàng)建堆

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

3、創(chuàng)建堆的時間復雜度

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

 二、堆的插入和刪除

1、堆的插入

• 將要插入的元素放在堆的最后，如果放不了，進行擴容
• 將新插入的節(jié)點向上調整，直到滿足堆的性質

 【向上調整】

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、堆的刪除

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

• 將堆頂元素和最后一個元素交換
• 堆的元素個數(shù)減一
• 對堆頂元素進行向下調整

 三、堆的應用

1、堆排序

升序：創(chuàng)建大根堆

降序：創(chuàng)建小根堆

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

2、top-k問題(求最小的K個數(shù))

top-k問題：求數(shù)據(jù)集合中前k個大或者小的元素，一般數(shù)據(jù)量都比較大。

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兩種類型的優(yōu)先級隊列。PriorityQueue是線程不安全的，PriorityBlockingQueue是線程安全的，本文主要介紹PriorityQueue。

【PriorityQueue】使用的注意事項：

• 必須導入PeioriryQueue的包；
• 放置的元素必須是能夠比較大小的，否則會拋出ClassCastException異常；
• 不能放置null元素，否則會拋出NullPointerException；
• 可以插入任意多的元素，內部會自動擴容；
• 底層使用了堆數(shù)據(jù)結構，默認是小堆。如果要構建大堆，則需要提供比較器。

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是默認的內部比較方式，如果用戶插入自定義類型對象時，該類對象必須要實現(xiàn)Comparble接口，并覆寫compareTo方法

2. 用戶也可以選擇使用比較器對象，如果用戶插入自定義類型對象時，必須要提供一個比較器類，讓該類實現(xiàn)Comparator接口并覆寫compare方法

// 用戶自己定義的比較器：直接實現(xiàn)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、優(yōu)先級隊列的構造

到此這篇關于Java 超詳細講解數(shù)據(jù)結構中的堆的應用的文章就介紹到這了,更多相關Java 堆的應用內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論