欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java堆&優(yōu)先級(jí)隊(duì)列示例講解(上)

 更新時(shí)間:2022年03月18日 11:24:47   作者:愛干飯的猿  
這篇文章主要通過示例詳細(xì)為大家介紹Java中的堆以及優(yōu)先級(jí)隊(duì)列,文中的示例代碼講解詳細(xì),對(duì)我們了解java有一定幫助,需要的可以參考一下

1. 二叉樹的順序存儲(chǔ)

1.1 存儲(chǔ)方式

使用數(shù)組保存二叉樹結(jié)構(gòu),方式即將二叉樹用 層序遍歷 方式放入數(shù)組中。

一般只適合表示完全二叉樹,這種方式的主要用法就是堆的表示。

因?yàn)榉峭耆鏄鋾?huì)有空間的浪費(fèi)(所有非完全二叉樹用鏈?zhǔn)酱鎯?chǔ))。

1.2 下標(biāo)關(guān)系

已知雙親 (parent) 的下標(biāo),則:

左孩子 (left) 下標(biāo) = 2 * parent + 1;

右孩子 (right) 下標(biāo) = 2 * parent + 2;

已知孩子(不區(qū)分左右) (child) 下標(biāo),則:

雙親 (parent) 下標(biāo) = (child - 1) / 2;

2. 堆(heap)

2.1 概念

1. 堆邏輯上是一棵完全二叉樹

2. 堆物理上是保存在數(shù)組中

3. 滿足任意結(jié)點(diǎn)的值都大于其子樹中結(jié)點(diǎn)的值,叫做大堆,或者大根堆,或者最大堆

4. 反之,則是小堆,或者小根堆,或者最小堆

5. 堆的基本作用是,快速找集合中的 最值

2.2 操作-(下沉&上?。┍纠亲畲蠖?/h3>

元素下沉:

     /**
     * 下沉操作
     */
    public void siftDown(int k){
        //還存在子樹
        while (leftChild(k) < data.size()){
            int j = leftChild(k);
            //判斷是否存在右子樹且大于左子樹的值
            if(j+1 < data.size() && data.get(j+1) > data.get(j)){
                j=j+1;
            }
            //此時(shí)j為左右子樹最大值
            //和當(dāng)前節(jié)點(diǎn)比較大小
            if(data.get(j) <= data.get(k)){
                break;
            }else {
                swap(k,j);
                k=j;
            }
        }
    }

元素上浮:

    /**
     * 上浮操作
     */
    // 上浮操作的終止條件: 已經(jīng)走到根節(jié)點(diǎn) || 當(dāng)前節(jié)點(diǎn)值 <= 父節(jié)點(diǎn)值
    // 循環(huán)的迭代條件 : 還存在父節(jié)點(diǎn)并且當(dāng)前節(jié)點(diǎn)值 > 父節(jié)點(diǎn)值
    private void siftUp(int k) {
        while (k>0 && data.get(k)>data.get(parent(k))){
            swap(k,parent(k));
            k=parent(k);
        }
    }

其中swap方法是交換操作:

    //交換三連
    private void swap(int i,int j) {
        int temp = data.get(j);
        data.set(j,data.get(i));
        data.set(i,temp);
    }

堆化數(shù)組:

    /**
     * 將任意數(shù)組堆化
     * @param arr
     */
    public MaxHeap(int[] arr){
        data = new ArrayList<>(arr.length);
        // 1.先將arr的所有元素復(fù)制到data數(shù)組中
        for(int i : arr){
            data.add(i);
        }
        // 2.從最后一個(gè)非葉子結(jié)點(diǎn)開始進(jìn)行siftDown
        for (int i = parent(data.size()-1); i >=0 ; i--) {
            siftDown(i);
        }
    }

圖示:

以此數(shù)組為例:

// 調(diào)整前
int[] array = { 27,15,19,18,28,34,65,49,25,37 };
// 調(diào)整后
int[] array = { 15,18,19,25,28,34,65,49,27,37 };

時(shí)間復(fù)雜度分析:

最壞的情況即圖示的情況,從根一路比較到葉子,比較的次數(shù)為完全二叉樹的高度

即時(shí)間復(fù)雜度為 O(log(n))

2.3 建堆-完整代碼(最大堆)

/**
 * 基于整形最大堆實(shí)現(xiàn)
 * 時(shí)根節(jié)點(diǎn)從0開始編號(hào),若此時(shí)節(jié)點(diǎn)編號(hào)為k
 * 左孩子為2k+1
 * 右孩子為2k+2
 * 父節(jié)點(diǎn)為(k-1)/2
 */
 
import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;
 
public class MaxHeap {
    // 使用JDK的動(dòng)態(tài)數(shù)組(ArrayList)來存儲(chǔ)一個(gè)最大堆
    List<Integer> data;
 
    // 構(gòu)造方法的this調(diào)用
    public MaxHeap(){
        this(10);
    }
    
    // 初始化的堆大小
    public MaxHeap(int size){
        data = new ArrayList<>(size);
    }
 
    /**
     * 將任意數(shù)組堆化
     * @param arr
     */
    public MaxHeap(int[] arr){
        data = new ArrayList<>(arr.length);
        // 1.先將arr的所有元素復(fù)制到data數(shù)組中
        for(int i : arr){
            data.add(i);
        }
        // 2.從最后一個(gè)非葉子結(jié)點(diǎn)開始進(jìn)行siftDown
        for (int i = parent(data.size()-1); i >=0 ; i--) {
            siftDown(i);
        }
    }
 
    /**
     * 向最大堆中增加值為Value的元素
     * @param value
     */
    public void add(int value){
        //1.先直接加到堆的末尾
        data.add(value);
        //2.元素上浮操作
        siftUp(data.size()-1);
    }
 
    /**
     * 只找到堆頂元素值
     * @return
     */
    public int peekMax (){
        if(isEmpty()){
            throw new NoSuchElementException("heap is empty!connot peek");
        }
        return data.get(0);
    }
 
    /**
     * 取出當(dāng)前最大堆的最大值
     */
    public int extractMax(){
        // 取值一定注意判空
        if(isEmpty()){
            throw new NoSuchElementException("heap is empty!connot extract");
        }
        int max = data.get(0);
        // 1.將數(shù)組末尾元素頂?shù)蕉秧?
        int lastValue =data.get(data.size()-1);
        data.set(0,lastValue);
        // 2.將數(shù)組末尾的元素刪除
        data.remove(data.size()-1);
        // 3.進(jìn)行元素的下沉操作
        siftDown(0);
        return max;
    }
 
    /**
     * 下沉操作
     */
    public void siftDown(int k){
        //還存在子樹
        while (leftChild(k) < data.size()){
            int j = leftChild(k);
            //判斷是否存在右子樹且大于左子樹的值
            if(j+1 < data.size() && data.get(j+1) > data.get(j)){
                j=j+1;
            }
            //此時(shí)j為左右子樹最大值
            //和當(dāng)前節(jié)點(diǎn)比較大小
            if(data.get(j) <= data.get(k)){
                break;
            }else {
                swap(k,j);
                k=j;
            }
        }
    }
 
    /**
     * 上浮操作
     */
    // 上浮操作的終止條件: 已經(jīng)走到根節(jié)點(diǎn) || 當(dāng)前節(jié)點(diǎn)值 <= 父節(jié)點(diǎn)值
    // 循環(huán)的迭代條件 : 還存在父節(jié)點(diǎn)并且當(dāng)前節(jié)點(diǎn)值 > 父節(jié)點(diǎn)值
    private void siftUp(int k) {
        while (k>0 && data.get(k)>data.get(parent(k))){
            swap(k,parent(k));
            k=parent(k);
        }
    }
 
    //交換三連
    private void swap(int i,int j) {
        int temp = data.get(j);
        data.set(j,data.get(i));
        data.set(i,temp);
    }
 
    //判讀堆為空
    public boolean isEmpty(){
        return data.size() == 0;
    }
    //根據(jù)索引找父節(jié)點(diǎn)
    public int parent(int k){
        return (k-1)>>1;
    }
    //根據(jù)索引找左孩子
    public int leftChild(int k){
        return k<<2+1;
    }
    //根據(jù)索引找右孩子
    public int rightChild(int k){
        return k<<2+2;
    }
 
    @Override
    public String toString() {
        return data.toString();
    }
}

ps:隨機(jī)數(shù)操作

        int[] data=new int[10000];
        //隨機(jī)數(shù)
        ThreadLocalRandom random = ThreadLocalRandom.current();
        for (int i = 0; i < data.length; i++) {
            data[i] = random.nextInt();
        }

3. 優(yōu)先級(jí)隊(duì)列

詳見下節(jié):Java堆&優(yōu)先級(jí)隊(duì)列示例講解(下)

到此這篇關(guān)于Java堆&優(yōu)先級(jí)隊(duì)列示例講解(上)的文章就介紹到這了,更多相關(guān)Java 堆 優(yōu)先級(jí)隊(duì)列內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • 基于Springboot使用logback的注意事項(xiàng)

    基于Springboot使用logback的注意事項(xiàng)

    這篇文章主要介紹了Springboot使用logback的注意事項(xiàng),具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2021-07-07
  • Java經(jīng)典面試題匯總:Spring MVC

    Java經(jīng)典面試題匯總:Spring MVC

    本篇總結(jié)的是Spring MVC框架相關(guān)的面試題,后續(xù)會(huì)持續(xù)更新,希望我的分享可以幫助到正在備戰(zhàn)面試的實(shí)習(xí)生或者已經(jīng)工作的同行,如果發(fā)現(xiàn)錯(cuò)誤還望大家多多包涵,不吝賜教,謝謝
    2021-07-07
  • 利用MyBatis進(jìn)行不同條件的like模糊查詢的方法

    利用MyBatis進(jìn)行不同條件的like模糊查詢的方法

    這篇文章主要介紹了利用MyBatis進(jìn)行不同條件的like模糊查詢,小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧
    2018-08-08
  • Springboot常用注解及作用說明

    Springboot常用注解及作用說明

    這篇文章主要介紹了Springboot常用注解及作用說明,Springboot開發(fā)中注解是非常重要的不可或缺的,那么Springboot中有哪些常用的注解呢,今天我們就來看一下這些注解和其作用,需要的朋友可以參考下
    2023-08-08
  • 使用@Validated 和 BindingResult 遇到的坑及解決

    使用@Validated 和 BindingResult 遇到的坑及解決

    這篇文章主要介紹了使用@Validated 和 BindingResult 遇到的坑及解決方案,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2021-10-10
  • Java Object類詳解_動(dòng)力節(jié)點(diǎn)Java學(xué)院整理

    Java Object類詳解_動(dòng)力節(jié)點(diǎn)Java學(xué)院整理

    Java作為一個(gè)龐大的知識(shí)體系,涉及到的知識(shí)點(diǎn)繁多,本文將從Java中最基本的類java.lang.Object開始談起,對(duì)java object類相關(guān)知識(shí)感興趣的朋友一起學(xué)習(xí)吧
    2017-04-04
  • Java文件(io)編程_文件字節(jié)流的使用方法

    Java文件(io)編程_文件字節(jié)流的使用方法

    下面小編就為大家?guī)硪黄狫ava文件(io)編程_文件字節(jié)流的使用方法。小編覺得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧
    2017-08-08
  • SpringMVC 重新定向redirect請(qǐng)求中攜帶數(shù)據(jù)方式

    SpringMVC 重新定向redirect請(qǐng)求中攜帶數(shù)據(jù)方式

    這篇文章主要介紹了SpringMVC 重新定向redirect請(qǐng)求中攜帶數(shù)據(jù)方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2021-12-12
  • Java 程序里transient關(guān)鍵字使用方法示例

    Java 程序里transient關(guān)鍵字使用方法示例

    這篇文章主要為大家介紹了Java 程序里transient關(guān)鍵字使用方法示例,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2023-11-11
  • 在java中使用SPI創(chuàng)建可擴(kuò)展的應(yīng)用程序操作

    在java中使用SPI創(chuàng)建可擴(kuò)展的應(yīng)用程序操作

    這篇文章主要介紹了在java中使用SPI創(chuàng)建可擴(kuò)展的應(yīng)用程序操作,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧
    2020-09-09

最新評(píng)論