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

Java深入了解數(shù)據(jù)結(jié)構(gòu)之優(yōu)先級隊(duì)列(堆)

 更新時(shí)間:2022年01月27日 15:27:50   作者:/少司命  
普通的隊(duì)列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu),元素在隊(duì)列尾追加,而從隊(duì)列頭刪除。在優(yōu)先隊(duì)列中,元素被賦予優(yōu)先級。當(dāng)訪問元素時(shí),具有最高優(yōu)先級的元素最先刪除。優(yōu)先隊(duì)列具有最高級先出 (first in, largest out)的行為特征。通常采用堆數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)

一,二叉樹的順序存儲

①存儲方式

使用數(shù)組保存二叉樹結(jié)構(gòu),方式即將二叉樹用層序遍歷方式放入數(shù)組中。 一般只適合表示完全二叉樹,因?yàn)榉峭耆鏄鋾锌臻g的浪費(fèi)。 這種方式的主要用法就是堆的表示。

②下標(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;

③二叉樹順序遍歷

// 層序遍歷
    void levelOrderTraversal(TreeNode root) {
        if(root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode top = queue.poll();
            System.out.print(top.val+" ");
            if(top.left != null) {
                queue.offer(top.left);
            }
            if(top.right!=null) {
                queue.offer(top.right);
            }
        }
        System.out.println();
    }

二,堆

①概念

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

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

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

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

②操作-向下調(diào)整

前提:

左右子樹必須已經(jīng)是一個(gè)堆,才能調(diào)整。

說明:

1. array 代表存儲堆的數(shù)組

2. size 代表數(shù)組中被視為堆數(shù)據(jù)的個(gè)數(shù)

3. index 代表要調(diào)整位置的下標(biāo)

4. left 代表 index 左孩子下標(biāo)

5. right 代表 index 右孩子下標(biāo)

6. min 代表 index 的最小值孩子的下標(biāo)?

過程(以小堆為例):

Ⅰ index 如果已經(jīng)是葉子結(jié)點(diǎn),則整個(gè)調(diào)整過程結(jié)束

1. 判斷 index 位置有沒有孩子

2. 因?yàn)槎咽峭耆鏄?,沒有左孩子就一定沒有右孩子,所以判斷是否有左孩子

3. 因?yàn)槎训拇鎯Y(jié)構(gòu)是數(shù)組,所以判斷是否有左孩子即判斷左孩子下標(biāo)是否越界,即 left >= size 越界

Ⅱ 確定 left 或 right,誰是 index 的最小孩子 min

1. 如果右孩子不存在,則 min = left

2. 否則,比較 array[left] 和 array[right] 值得大小,選擇小的為 min

Ⅲ比較 array[index] 的值 和 array[min] 的值,如果 array[index] <= array[min],則滿足堆的性質(zhì),調(diào)整結(jié)束

Ⅳ否則,交換 array[index] 和 array[min] 的值

Ⅴ然后因?yàn)?min 位置的堆的性質(zhì)可能被破壞,所以把 min 視作 index,向下重復(fù)以上過程

向下調(diào)整是以層序遍歷的二叉樹為例來遍歷

public void adjustDown(int root,int len){
        int parent = root;
        int child = 2*parent + 1;
        while(child < len){
            if (child + 1 < len && this.elem[child] < this.elem[child + 1] ){
                child++;
            }
            if(this.elem[child] > this.elem[parent]){
                int tmp = this.elem[parent];
                this.elem[parent] = this.elem[child];
                this.elem[child] = tmp;
                parent = child;
                child = 2*parent + 1;
            }else{
                break;
            }
        }
    }

③建堆(建大堆為例)

下面我們給出一個(gè)數(shù)組,這個(gè)數(shù)組邏輯上可以看做一顆完全二叉樹,但是還不是一個(gè)堆,現(xiàn)在我們通過算法,把它構(gòu) 建成一個(gè)堆。根節(jié)點(diǎn)左右子樹不是堆,我們怎么調(diào)整呢?這里我們從倒數(shù)的第一個(gè)非葉子節(jié)點(diǎn)的子樹開始調(diào)整,一直 調(diào)整到根節(jié)點(diǎn)的樹,就可以調(diào)整成堆。

//建大堆
    public void creatHeap(int[] array){
        for (int i = 0; i < array.length;i++){
            this.elem[i] = array[i];
            suedSize++;
        }
        for (int parent = (array.length - 1 - 1) / 2;parent >= 0;parent--){
            adjustDown(parent,this.suedSize);
        }

三,堆的應(yīng)用-優(yōu)先級隊(duì)列

①概念

在很多應(yīng)用中,我們通常需要按照優(yōu)先級情況對待處理對象進(jìn)行處理,比如首先處理優(yōu)先級最高的對象,然后處理次 高的對象。最簡單的一個(gè)例子就是,在手機(jī)上玩游戲的時(shí)候,如果有來電,那么系統(tǒng)應(yīng)該優(yōu)先處理打進(jìn)來的電話。 在這種情況下,我們的數(shù)據(jù)結(jié)構(gòu)應(yīng)該提供兩個(gè)最基本的操作,一個(gè)是返回最高優(yōu)先級對象,一個(gè)是添加新的對象。這 種數(shù)據(jù)結(jié)構(gòu)就是優(yōu)先級隊(duì)列(Priority Queue)

②內(nèi)部原理

優(yōu)先級隊(duì)列的實(shí)現(xiàn)方式有很多,但最常見的是使用堆來構(gòu)建。

③入隊(duì)列

過程(以大堆為例):

1. 首先按尾插方式放入數(shù)組

2. 比較其和其雙親的值的大小,如果雙親的值大,則滿足堆的性質(zhì),插入結(jié)束

3. 否則,交換其和雙親位置的值,重新進(jìn)行 2、3 步驟 4. 直到根結(jié)點(diǎn)

public void adjustUp(int child){
        int parent = (child - 1) / 2;
        while(child>0){
            if(this.elem[child] > this.elem[parent]){
                int tmp = this.elem[parent];
                this.elem[parent] = this.elem[child];
                this.elem[child] = tmp;
                child = parent;
                parent = (child - 1) / 2;
            }else {
                break;
            }
        }
    }
public void push(int val) {
        if (isFull()) {
            this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length);
            this.elem[this.suedSize] = val;
            this.suedSize++;
            adjustUp(this.suedSize - 1);
 
        }
    }

④出隊(duì)列(優(yōu)先級最高)

為了防止破壞堆的結(jié)構(gòu),刪除時(shí)并不是直接將堆頂元素刪除,而是用數(shù)組的最后一個(gè)元素替換堆頂元素,然后通過向下調(diào)整方式重新調(diào)整成堆

 public boolean isEmpty(){
        return this.suedSize == 0;
    }
 public void pop(){
        if(isEmpty()){
            return;
        }
        int tmp = this.elem[0];
        this.elem[0] = this.elem[this.suedSize-1];
        this.elem[this.suedSize-1] = tmp;
        this.suedSize--;
        adjustDown(0,this.suedSize);
    }

⑤返回隊(duì)首元素(優(yōu)先級最高)

public int peek(){
        if(isEmpty()){
            return -1;
        }
        return this.elem[0];
    }
  public boolean isFull(){
        return this.suedSize == this.elem.length;
    }

四,堆排序

 /**
     * 一定是先創(chuàng)建大堆
     *      調(diào)整每棵樹
     * 開始堆排序:
     *     先交換  后調(diào)整  直到 0下標(biāo)
     */
 
    public void heapSort(){
        int end = this.suedSize-1;
        while (end > 0){
            int tmp = this.elem[0];
            this.elem[0] = this.elem[end];
            this.elem[end] = tmp;
            adjustDown(0,end);
            end--;
 
        }
 
    }

到此這篇關(guān)于Java深入了解數(shù)據(jù)結(jié)構(gòu)之優(yōu)先級隊(duì)列(堆)的文章就介紹到這了,更多相關(guān)Java 優(yōu)先級隊(duì)列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • 理解Java設(shè)計(jì)模式編程中的迪米特原則

    理解Java設(shè)計(jì)模式編程中的迪米特原則

    這篇文章主要介紹了Java設(shè)計(jì)模式編程中的迪米特原則,迪米特原則旨在降低類與類之間的耦合,需要的朋友可以參考下
    2016-02-02
  • JavaWeb監(jiān)聽器Listener實(shí)例解析

    JavaWeb監(jiān)聽器Listener實(shí)例解析

    這篇文章主要為大家詳細(xì)介紹了JavaWeb監(jiān)聽器Listener實(shí)例,針對監(jiān)聽器進(jìn)行進(jìn)行細(xì)致分析,感興趣的小伙伴們可以參考一下
    2016-08-08
  • Springboot整合多數(shù)據(jù)源配置流程詳細(xì)講解

    Springboot整合多數(shù)據(jù)源配置流程詳細(xì)講解

    這篇文章主要介紹了Springboot整合多數(shù)據(jù)源配置流程,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)吧
    2023-03-03
  • Java?實(shí)現(xiàn)字符串SHA1加密方法

    Java?實(shí)現(xiàn)字符串SHA1加密方法

    這篇文章主要介紹了Java?實(shí)現(xiàn)字符串SHA1加密方法,具有很好的參考價(jià)值,希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2021-11-11
  • 解決springboot自定義注解AOP在controller上導(dǎo)致controller注入失敗問題

    解決springboot自定義注解AOP在controller上導(dǎo)致controller注入失敗問題

    這篇文章主要介紹了解決springboot自定義注解AOP在controller上導(dǎo)致controller注入失敗問題,具有很好的參考價(jià)值,希望對大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2023-10-10
  • Java使用EasyExcel進(jìn)行單元格合并的問題詳解

    Java使用EasyExcel進(jìn)行單元格合并的問題詳解

    項(xiàng)目中需要導(dǎo)出并合并指定的單元格,下面這篇文章主要給大家介紹了關(guān)于java評論、回復(fù)功能設(shè)計(jì)與實(shí)現(xiàn)的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下
    2022-06-06
  • Java生成圖形驗(yàn)證碼工具類

    Java生成圖形驗(yàn)證碼工具類

    這篇文章主要介紹了Java生成圖形驗(yàn)證碼工具類,本文思路明確介紹的非常詳細(xì),需要的朋友可以參考下
    2017-02-02
  • SpringBoot3?Web編程開發(fā)的工程搭建攔截器及測試工具示例

    SpringBoot3?Web編程開發(fā)的工程搭建攔截器及測試工具示例

    這篇文章主要介紹了SpringBoot3?Web編程開發(fā)的工程搭建攔截器及測試工具示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2023-08-08
  • Springboot整合Shiro的代碼實(shí)例

    Springboot整合Shiro的代碼實(shí)例

    這篇文章主要介紹了Springboot整合Shiro的代碼實(shí)例,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2019-10-10
  • Lucene單值編碼壓縮算法源碼解析

    Lucene單值編碼壓縮算法源碼解析

    這篇文章主要為大家介紹了Lucene單值編碼壓縮算法源碼解析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2022-11-11

最新評論