" />

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

深入了解Java數(shù)據(jù)結(jié)構(gòu)和算法之堆

 更新時(shí)間:2022年01月21日 15:19:26   作者:YSOcean  
這篇文章主要為大家介紹了Java數(shù)據(jù)結(jié)構(gòu)和算法之堆 ,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來幫助

1、堆的定義

①、它是完全二叉樹,除了樹的最后一層節(jié)點(diǎn)不需要是滿的,其它的每一層從左到右都是滿的。注意下面兩種情況,第二種最后一層從左到右中間有斷隔,那么也是不完全二叉樹。

②、它通常用數(shù)組來實(shí)現(xiàn)?! ?/p>

這種用數(shù)組實(shí)現(xiàn)的二叉樹,假設(shè)節(jié)點(diǎn)的索引值為index,那么:

節(jié)點(diǎn)的左子節(jié)點(diǎn)是 2*index+1,

節(jié)點(diǎn)的右子節(jié)點(diǎn)是 2*index+2,

節(jié)點(diǎn)的父節(jié)點(diǎn)是 (index-1)/2。

③、堆中的每一個(gè)節(jié)點(diǎn)的關(guān)鍵字都大于(或等于)這個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)的關(guān)鍵字。

這里要注意堆和前面說的二叉搜索樹的區(qū)別,二叉搜索樹中所有節(jié)點(diǎn)的左子節(jié)點(diǎn)關(guān)鍵字都小于右子節(jié)點(diǎn)關(guān)鍵字,在二叉搜索樹中通過一個(gè)簡(jiǎn)單的算法就可以按序遍歷節(jié)點(diǎn)。但是在堆中,按序遍歷節(jié)點(diǎn)是很困難的,如上圖所示,堆只有沿著從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的每一條路徑是降序排列的,指定節(jié)點(diǎn)的左邊節(jié)點(diǎn)或者右邊節(jié)點(diǎn),以及上層節(jié)點(diǎn)或者下層節(jié)點(diǎn)由于不在同一條路徑上,他們的關(guān)鍵字可能比指定節(jié)點(diǎn)大或者小。所以相對(duì)于二叉搜索樹,堆是弱序的。

2、遍歷和查找

前面我們說了,堆是弱序的,所以想要遍歷堆是很困難的,基本上,堆是不支持遍歷的。

對(duì)于查找,由于堆的特性,在查找的過程中,沒有足夠的信息來決定選擇通過節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)中的哪一個(gè)來選擇走向下一層,所以也很難在堆中查找到某個(gè)關(guān)鍵字。

因此,堆這種組織似乎非常接近無序,不過,對(duì)于快速的移除最大(或最小)節(jié)點(diǎn),也就是根節(jié)點(diǎn),以及能快速插入新的節(jié)點(diǎn),這兩個(gè)操作就足夠了。

3、移除

移除是指刪除關(guān)鍵字最大的節(jié)點(diǎn)(或最?。?,也就是根節(jié)點(diǎn)。

根節(jié)點(diǎn)在數(shù)組中的索引總是0,即maxNode = heapArray[0];

移除根節(jié)點(diǎn)之后,那樹就空了一個(gè)根節(jié)點(diǎn),也就是數(shù)組有了一個(gè)空的數(shù)據(jù)單元,這個(gè)空單元我們必須填上。

第一種方法:將數(shù)組所有數(shù)據(jù)項(xiàng)都向前移動(dòng)一個(gè)單元,這比較費(fèi)時(shí)。

第二種方法:

  • ①、移走根
  • ②、把最后一個(gè)節(jié)點(diǎn)移動(dòng)到根的位置
  • ③、一直向下篩選這個(gè)節(jié)點(diǎn),直到它在一個(gè)大于它的節(jié)點(diǎn)之下,小于它的節(jié)點(diǎn)之上為止。

具體步驟如下:

圖a表示把最后一個(gè)節(jié)點(diǎn)移到根節(jié)點(diǎn),圖b、c、d表示將節(jié)點(diǎn)向下篩選到合適的位置,它的合適位置在最底層(有時(shí)候可能在中間),圖e表示節(jié)點(diǎn)在正確位置的情景。

注意:向下篩選的時(shí)候,將目標(biāo)節(jié)點(diǎn)和其子節(jié)點(diǎn)比較,誰大就和誰交換位置。

4、插入

插入節(jié)點(diǎn)也很容易,插入時(shí),選擇向上篩選,節(jié)點(diǎn)初始時(shí)插入到數(shù)組最后第一個(gè)空著的單元,數(shù)組容量大小增一。然后進(jìn)行向上篩選的算法。

注意:向上篩選和向下不同,向上篩選只用和一個(gè)父節(jié)點(diǎn)進(jìn)行比較,比父節(jié)點(diǎn)小就停止篩選了。

5、完整的Java堆代碼

首先我們要知道用數(shù)組表示堆的一些要點(diǎn)。若數(shù)組中節(jié)點(diǎn)的索引為x,則:

節(jié)點(diǎn)的左子節(jié)點(diǎn)是 2*index+1,

節(jié)點(diǎn)的右子節(jié)點(diǎn)是 2*index+2,

節(jié)點(diǎn)的父節(jié)點(diǎn)是 (index-1)/2。

注意:"/" 這個(gè)符號(hào),應(yīng)用于整數(shù)的算式時(shí),它執(zhí)行整除,且得到是是向下取整的值。

package com.ys.tree.heap;
 
public class Heap {
     
    private Node[] heapArray;
    private int maxSize;
    private int currentSize;
     
    public Heap(int mx) {
        maxSize = mx;
        currentSize = 0;
        heapArray = new Node[maxSize];
    }
     
    public boolean isEmpty() {
        return (currentSize == 0)? true : false;
    }
     
    public boolean isFull() {
        return (currentSize == maxSize)? true : false;
    }
     
    public boolean insert(int key) {
        if(isFull()) {
            return false;
        }
        Node newNode = new Node(key);
        heapArray[currentSize] = newNode;
        trickleUp(currentSize++);
        return true;
    }
    //向上調(diào)整
    public void trickleUp(int index) {
        int parent = (index - 1) / 2; //父節(jié)點(diǎn)的索引
        Node bottom = heapArray[index]; //將新加的尾節(jié)點(diǎn)存在bottom中
        while(index > 0 && heapArray[parent].getKey() < bottom.getKey()) {
            heapArray[index] = heapArray[parent];
            index = parent;
            parent = (parent - 1) / 2;
        }
        heapArray[index] = bottom;
    }
     
    public Node remove() {
        Node root = heapArray[0];
        heapArray[0] = heapArray[--currentSize];
        trickleDown(0);
        return root;
    }
    //向下調(diào)整
    public void trickleDown(int index) {
        Node top = heapArray[index];
        int largeChildIndex;
        while(index < currentSize/2) { //while node has at least one child
            int leftChildIndex = 2 * index + 1;
            int rightChildIndex = leftChildIndex + 1;
            //find larger child
            if(rightChildIndex < currentSize &&  //rightChild exists?
                    heapArray[leftChildIndex].getKey() < heapArray[rightChildIndex].getKey()) {
                largeChildIndex = rightChildIndex;
            }
            else {
                largeChildIndex = leftChildIndex;
            }
            if(top.getKey() >= heapArray[largeChildIndex].getKey()) {
                break;
            }
            heapArray[index] = heapArray[largeChildIndex];
            index = largeChildIndex;
        }
        heapArray[index] = top;
    }
    //根據(jù)索引改變堆中某個(gè)數(shù)據(jù)
    public boolean change(int index, int newValue) {
        if(index < 0 || index >= currentSize) {
            return false;
        }
        int oldValue = heapArray[index].getKey();
        heapArray[index].setKey(newValue);
        if(oldValue < newValue) {
            trickleUp(index);
        }
        else {
            trickleDown(index);
        }
        return true;
    }
     
    public void displayHeap() {
        System.out.println("heapArray(array format): ");
        for(int i = 0; i < currentSize; i++) {
            if(heapArray[i] != null) {
                System.out.print(heapArray[i].getKey() + " ");
            }
            else {
                System.out.print("--");
            }
        }
    }
}
class Node {
    private int iData;
    public Node(int key) {
        iData = key;
    }
     
    public int getKey() {
        return iData;
    }
     
    public void setKey(int key) {
        iData = key;
    }
}

總結(jié)

本篇文章就到這里了,希望能夠給你帶來幫助,也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!

相關(guān)文章

  • JVM入門之類加載與字節(jié)碼技術(shù)(類加載與類的加載器)

    JVM入門之類加載與字節(jié)碼技術(shù)(類加載與類的加載器)

    Java字節(jié)碼增強(qiáng)指的是在Java字節(jié)碼生成之后,對(duì)其進(jìn)行修改,增強(qiáng)其功能,這種方式相當(dāng)于對(duì)應(yīng)用程序的二進(jìn)制文件進(jìn)行修改。Java字節(jié)碼增強(qiáng)主要是為了減少冗余代碼,提高性能等
    2021-06-06
  • 解決java字符串轉(zhuǎn)換成時(shí)間Unparseable date出錯(cuò)的問題

    解決java字符串轉(zhuǎn)換成時(shí)間Unparseable date出錯(cuò)的問題

    這篇文章主要介紹了解決java字符串轉(zhuǎn)換成時(shí)間Unparseable date出錯(cuò)的問題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2021-06-06
  • JAVA MyBatis入門學(xué)習(xí)過程記錄

    JAVA MyBatis入門學(xué)習(xí)過程記錄

    MyBatis是一個(gè)支持普通SQL查詢,存儲(chǔ)過程和高級(jí)映射的優(yōu)秀持久層框架。這篇文章主要介紹了mybatis框架入門學(xué)習(xí)教程,需要的朋友可以參考下,希望能幫助到你
    2021-06-06
  • Spring Boot集成Quartz注入Spring管理的類的方法

    Spring Boot集成Quartz注入Spring管理的類的方法

    本篇文章主要介紹了Spring Boot集成Quartz注入Spring管理的類的方法,小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧
    2018-04-04
  • SpringBoot整合Mybatis Plus實(shí)現(xiàn)基本CRUD的示例代碼

    SpringBoot整合Mybatis Plus實(shí)現(xiàn)基本CRUD的示例代碼

    Mybatis Plus是在Mybatis的基礎(chǔ)上的增強(qiáng),使得我們對(duì)一些基本的CRUD使用起來更方便,本文主要介紹了SpringBoot整合Mybatis Plus實(shí)現(xiàn)基本CRUD的示例代碼,具有一定的參考價(jià)值,感興趣的可以了解一下
    2023-05-05
  • Java線程之ThreadLocal解析

    Java線程之ThreadLocal解析

    這篇文章主要介紹了Java線程之ThreadLocal解析,ThreadLocal 提供線程的局部變量,每個(gè)線程都可以通過get()和set()對(duì)局部變量進(jìn)行操作而不會(huì)對(duì)其他線程的局部變量產(chǎn)生影響,實(shí)現(xiàn)了線程之間的數(shù)據(jù)隔離,需要的朋友可以參考下
    2023-09-09
  • springBoot 與neo4j的簡(jiǎn)單整合示例

    springBoot 與neo4j的簡(jiǎn)單整合示例

    這篇文章主要介紹了springBoot 與neo4j的簡(jiǎn)單整合示例,小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧
    2019-01-01
  • 一篇文章徹底弄懂Java中二叉樹

    一篇文章徹底弄懂Java中二叉樹

    二叉樹是有限個(gè)節(jié)點(diǎn)的集合,這個(gè)集合可以是空集,也可以是一個(gè)根節(jié)點(diǎn)和兩顆不相交的子二叉樹組成的集合,其中一顆樹叫根的左子樹,另一顆樹叫右子樹,這篇文章主要給大家介紹了一篇文章如何徹底弄懂Java中二叉樹的相關(guān)資料,需要的朋友可以參考下
    2022-01-01
  • 最新評(píng)論