一、堆的創(chuàng)建

1、向下調(diào)整（以小堆為例）  

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

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

• parent右孩子是否存在，存在找到左右孩子中最小的孩子，讓child進(jìn)行標(biāo)記
• 將parent與較小的孩子child比較，如果：

parent小于較小的孩子child，調(diào)整結(jié)束否則：交換parent與較小的孩子child，交換完成之后，parent中大的元素向下移動(dòng)，可能導(dǎo)致子樹不滿足堆的性質(zhì)，因此需要繼續(xù)向下調(diào)整，即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)建堆

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

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

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

 二、堆的插入和刪除

1、堆的插入

• 將要插入的元素放在堆的最后，如果放不了，進(jìn)行擴(kuò)容
• 將新插入的節(jié)點(diǎn)向上調(diào)整，直到滿足堆的性質(zhì)

 【向上調(diào)整】

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ù)堆的性質(zhì)，對(duì)刪除的一定是堆頂元素。步驟如下：

• 將堆頂元素和最后一個(gè)元素交換
• 堆的元素個(gè)數(shù)減一
• 對(duì)堆頂元素進(jìn)行向下調(diào)整

 三、堆的應(yīng)用

1、堆排序

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

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

交換堆頂元素和堆得最后一個(gè)元素，進(jìn)行向下調(diào)整，直到堆有序。

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

top-k問題：求數(shù)據(jù)集合中前k個(gè)大或者小的元素，一般數(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)先級(jí)隊(duì)列。PriorityQueue是線程不安全的，PriorityBlockingQueue是線程安全的，本文主要介紹PriorityQueue。

【PriorityQueue】使用的注意事項(xiàng)：

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

PriorityQueue的擴(kuò)容方式：

• 如果容量小于64時(shí)，是按照oldCapacity的2倍方式擴(kuò)容的
• 如果容量大于等于64，是按照oldCapacity的1.5倍方式擴(kuò)容的
• 如果容量超過MAX_ARRAY_SIZE，按照MAX_ARRAY_SIZE來進(jìn)行擴(kuò)容

int newCapacity = oldCapacity + ((oldCapacity < 64) ?

                      (oldCapacity + 2) : 

                   (oldCapacity >> 1));

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

1. Comparble是默認(rèn)的內(nèi)部比較方式，如果用戶插入自定義類型對(duì)象時(shí)，該類對(duì)象必須要實(shí)現(xiàn)Comparble接口，并覆寫compareTo方法

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

// 用戶自己定義的比較器：直接實(shí)現(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)先級(jí)隊(duì)列的構(gòu)造

到此這篇關(guān)于Java 超詳細(xì)講解數(shù)據(jù)結(jié)構(gòu)中的堆的應(yīng)用的文章就介紹到這了,更多相關(guān)Java 堆的應(yīng)用內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論