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

Java實現(xiàn)二叉堆、大頂堆和小頂堆

 更新時間：2022年01月26日 17:05:50   作者：炒雞辣雞123  
二叉堆就是完全二叉樹，或者是靠近完全二叉樹結(jié)構(gòu)的二叉樹。大頂堆要求對于一個節(jié)點來說，它的左右節(jié)點都比它??；小頂堆要求對于一個節(jié)點來說，它的左右節(jié)點都比它大。本文將用Java分別實現(xiàn)二叉堆、大頂堆和小頂堆。需要的可以參考一下

什么是二叉堆

二叉堆就是完全二叉樹，或者是靠近完全二叉樹結(jié)構(gòu)的二叉樹。在二叉樹建樹時采取前序建樹就是建立的完全二叉樹。也就是二叉堆。所以二叉堆的建堆過程理論上講和前序建樹一樣。

什么是大頂堆、小頂堆

二叉堆本質(zhì)上是一棵近完全的二叉樹，那么大頂堆和小頂堆必然也是滿足這個結(jié)構(gòu)要求的。在此之上，大頂堆要求對于一個節(jié)點來說，它的左右節(jié)點都比它??；小頂堆要求對于一個節(jié)點來說，它的左右節(jié)點都比它大。

建堆

二叉堆建堆本質(zhì)上和前序建堆差不多，只不過需要考慮的一點就是大小關(guān)系，這一點和二叉搜索樹建樹有點相似，所以可以得出結(jié)論，建樹，本質(zhì)上都是遞歸建樹，只不過因為數(shù)據(jù)結(jié)構(gòu)的大小要求不一樣，需要的判斷函數(shù)不一樣，節(jié)點進入哪個位置也不一樣。

大頂堆和小頂堆也分為穩(wěn)定和不穩(wěn)定的堆。穩(wěn)定和不穩(wěn)定指如果具備相同的值，那么他們的插入順序應(yīng)該和節(jié)點順序一致。

程序?qū)崿F(xiàn)

首先，定義出基本的堆結(jié)構(gòu)

public class BinaryHeap {

? ? private Integer value;

? ? private BinaryHeap leftChild;
? ? private BinaryHeap rightChild;
}

建堆過程與建二叉樹過程一致

public static BinaryHeap buildHeap(BinaryHeap binaryHeap, Integer value) {
? ? if (Objects.isNull(binaryHeap)) binaryHeap = new BinaryHeap();
? ? if (Objects.isNull(binaryHeap.getValue())) {
? ? ? ? binaryHeap.setValue(value);
? ? ? ? return binaryHeap;
? ? }
? ? if (Objects.isNull(binaryHeap.getLeftChild())) {
? ? ? ? BinaryHeap binaryHeap1 = new BinaryHeap();
? ? ? ? binaryHeap1.setValue(value);
? ? ? ? binaryHeap.setLeftChild(binaryHeap1);
? ? } else if (Objects.nonNull(binaryHeap.getLeftChild())) {
? ? ? ? if (Objects.isNull(binaryHeap.getRightChild())) {
? ? ? ? ? ? BinaryHeap binaryHeap1 = new BinaryHeap();
? ? ? ? ? ? binaryHeap1.setValue(value);
? ? ? ? ? ? binaryHeap.setRightChild(binaryHeap1);
? ? ? ? } else {
? ? ? ? ? ? // TODO: 2022/1/14 左右節(jié)點兩種都不為null
? ? ? ? ? ? if (checkNull(binaryHeap.getLeftChild())) buildHeap(binaryHeap.getLeftChild(), value);
? ? ? ? ? ? else if (checkNull(binaryHeap.getRightChild())) buildHeap(binaryHeap.getRightChild(), value);
? ? ? ? ? ? else buildHeap(binaryHeap.getLeftChild(), value);
? ? ? ? }

? ? }
? ? return binaryHeap;
}

主要原理就是如果當(dāng)前節(jié)點的左節(jié)點為空，則把當(dāng)前值放到左節(jié)點，如果左節(jié)點不為空，右節(jié)點為空，則把值放到右節(jié)點。如果左右節(jié)點都不為空，就將建樹過程轉(zhuǎn)移到下一層，如果左節(jié)點有為空的子節(jié)點，就轉(zhuǎn)移給左節(jié)點，如果左節(jié)點沒有為空的子節(jié)點，且右節(jié)點有為空的子節(jié)點，那么轉(zhuǎn)移給右節(jié)點。如果左右節(jié)點都沒有為空的子節(jié)點，那么也轉(zhuǎn)移給左節(jié)點。

以序列2,3,4,5,9,6,8,7為例，按照該算法建立出來的二叉堆結(jié)構(gòu)如下：

{
    "value": 2,
    "left_child": {
        "value": 3,
        "left_child": {
            "value": 4,
            "left_child": {
                "value": 8,
                "left_child": null,
                "right_child": null
            },
            "right_child": {
                "value": 7,
                "left_child": null,
                "right_child": null
            }
        },
        "right_child": {
            "value": 5,
            "left_child": null,
            "right_child": null
        }
    },
    "right_child": {
        "value": 1,
        "left_child": {
            "value": 9,
            "left_child": null,
            "right_child": null
        },
        "right_child": {
            "value": 6,
            "left_child": null,
            "right_child": null
        }
    }
}

建立大頂堆

大頂堆在建堆的基礎(chǔ)上，有一個要求，根節(jié)點比左右子樹的任何節(jié)點的值都大。那么建樹的過程可以分為兩步，對于每一個值，首先按照建樹過程，會到二叉堆的最底部，然后通過不斷的讓自己與自己的根節(jié)點做比較，如果自己大于根節(jié)點，就交換自己與根節(jié)點的位置，遞歸回溯即可。

邏輯過程

假設(shè)現(xiàn)在紅色節(jié)點組成的已經(jīng)是一個大頂堆，現(xiàn)在新增了一個節(jié)點到這個二叉堆中，而且是比任意節(jié)點都大，那么黑色箭頭將是該節(jié)點的行動路線，它會反復(fù)與父級比較，如果大于父級，則交換和父級的關(guān)系。

程序?qū)崿F(xiàn)

public static BinaryHeap up(BinaryHeap father) {
  if (Objects.nonNull(father.getLeftChild())) {
    if (father.getValue() < father.getLeftChild().getValue()) {
      int c = father.getValue();
      father.setValue(father.getLeftChild().getValue());
      father.getLeftChild().setValue(c);
    }
    up(father.getLeftChild());
  }
  if (Objects.nonNull(father.getRightChild())) {
    if (father.getValue() < father.getRightChild().getValue()) {
      int c = father.getValue();
      father.setValue(father.getRightChild().getValue());
      father.getRightChild().setValue(c);
    }
    up(father.getRightChild());
  }
  return father;
}

該方法放在普通建樹方法之后，就是大頂堆的建樹方法了，總的方法如下：

public static BinaryHeap bigPush(BinaryHeap binaryHeap, Integer value) {
    binaryHeap = buildHeap(binaryHeap, value);
    up(binaryHeap);
    return binaryHeap;
}

還是以序列2,3,4,5,9,6,8,7為例，按照該算法建立出來的大頂堆結(jié)構(gòu)如下：

{
    "value": 9,
    "left_child": {
        "value": 8,
        "left_child": {
            "value": 7,
            "left_child": {
                "value": 2,
                "left_child": null,
                "right_child": null
            },
            "right_child": {
                "value": 4,
                "left_child": null,
                "right_child": null
            }
        },
        "right_child": {
            "value": 3,
            "left_child": null,
            "right_child": null
        }
    },
    "right_child": {
        "value": 6,
        "left_child": {
            "value": 1,
            "left_child": null,
            "right_child": null
        },
        "right_child": {
            "value": 5,
            "left_child": null,
            "right_child": null
        }
    }
}

建立小頂堆

小頂堆與大頂堆類似

邏輯過程

過程與大頂堆一致，不過此時是比父級小就和父級交換。

程序?qū)崿F(xiàn)

public static BinaryHeap down(BinaryHeap father) {
    if (Objects.nonNull(father.getLeftChild())) {
        if (father.getValue() > father.getLeftChild().getValue()) {
            int c = father.getValue();
            father.setValue(father.getLeftChild().getValue());
            father.getLeftChild().setValue(c);
        }
        down(father.getLeftChild());
    }
    if (Objects.nonNull(father.getRightChild())) {
        if (father.getValue() > father.getRightChild().getValue()) {
            int c = father.getValue();
            father.setValue(father.getRightChild().getValue());
            father.getRightChild().setValue(c);
        }
        down(father.getRightChild());
    }
    return father;
}

這個是向下走的過程，最終代碼為：

public static BinaryHeap smallPush(BinaryHeap binaryHeap, Integer value) {
    binaryHeap = buildHeap(binaryHeap, value);
    down(binaryHeap);
    return binaryHeap;
}

以序列2,3,4,5,9,6,8,7為例，按照該算法建立出來的小頂堆結(jié)構(gòu)如下：

{
    "value": 1,
    "left_child": {
        "value": 3,
        "left_child": {
            "value": 4,
            "left_child": {
                "value": 8,
                "left_child": null,
                "right_child": null
            },
            "right_child": {
                "value": 7,
                "left_child": null,
                "right_child": null
            }
        },
        "right_child": {
            "value": 5,
            "left_child": null,
            "right_child": null
        }
    },
    "right_child": {
        "value": 2,
        "left_child": {
            "value": 9,
            "left_child": null,
            "right_child": null
        },
        "right_child": {
            "value": 6,
            "left_child": null,
            "right_child": null
        }
    }
}

從堆頂取數(shù)據(jù)并重構(gòu)大小頂堆

public static Integer bigPop(BinaryHeap binaryHeap) {
    Integer val = binaryHeap.getValue();
    if (binaryHeap.getLeftChild().getValue() >= binaryHeap.getRightChild().getValue()) {
        binaryHeap.setValue(binaryHeap.getLeftChild().getValue());
        BinaryHeap binaryHeap1 = mergeTree(binaryHeap.getLeftChild().getLeftChild(), binaryHeap.getLeftChild().getRightChild());
        up(binaryHeap1);
        binaryHeap.setLeftChild(binaryHeap1);
    } else {
        binaryHeap.setValue(binaryHeap.getRightChild().getValue());
        BinaryHeap binaryHeap1 = mergeTree(binaryHeap.getRightChild().getLeftChild(), binaryHeap.getRightChild().getRightChild());
        up(binaryHeap1);
        binaryHeap.setRightChild(binaryHeap1);
    }
    return val;
}

public static Integer smallPop(BinaryHeap binaryHeap) {
    Integer val = binaryHeap.getValue();
    if (binaryHeap.getLeftChild().getValue() <= binaryHeap.getRightChild().getValue()) {
        binaryHeap.setValue(binaryHeap.getLeftChild().getValue());
        BinaryHeap binaryHeap1 = mergeTree(binaryHeap.getLeftChild().getLeftChild(), binaryHeap.getLeftChild().getRightChild());
        down(binaryHeap1);
        binaryHeap.setLeftChild(binaryHeap1);
    } else {
        binaryHeap.setValue(binaryHeap.getRightChild().getValue());
        BinaryHeap binaryHeap1 = mergeTree(binaryHeap.getRightChild().getLeftChild(), binaryHeap.getRightChild().getRightChild());
        down(binaryHeap1);
        binaryHeap.setRightChild(binaryHeap1);
    }
    return val;

}

取出來之后，需要重新調(diào)用down或者up函數(shù)。以構(gòu)建小頂堆，取出五次后的結(jié)果

public static void main(String[] args) {
        int[] a = new int[]{2, 3, 1, 4, 5, 9, 6, 8, 7};

        BinaryHeap binaryHeap = new BinaryHeap();
        for (int i = 0; i < a.length; i++) {
            binaryHeap = smallPush(binaryHeap, a[i]);
        }
        System.out.println(Json.toJson(smallPop(binaryHeap)));
        System.out.println(Json.toJson(smallPop(binaryHeap)));
        System.out.println(Json.toJson(smallPop(binaryHeap)));
        System.out.println(Json.toJson(smallPop(binaryHeap)));
        System.out.println(Json.toJson(smallPop(binaryHeap)));
        System.out.println(Json.toJson(binaryHeap));
    }

取完后的小頂堆為：

{
    "value": 6,
    "left_child": {
        "value": 7,
        "left_child": {
            "value": 8,
            "left_child": null,
            "right_child": null
        },
        "right_child": null
    },
    "right_child": {
        "value": 9,
        "left_child": null,
        "right_child": null
    }
}

到此這篇關(guān)于Java實現(xiàn)二叉堆、大頂堆和小頂堆的文章就介紹到這了,更多相關(guān)Java內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

相關(guān)文章

  • java中map和對象互轉(zhuǎn)工具類的實現(xiàn)示例

    java中map和對象互轉(zhuǎn)工具類的實現(xiàn)示例

    這篇文章主要介紹了java中map和對象互轉(zhuǎn)工具類的實現(xiàn)示例，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2019-08-08
  • Springboot+mybatis plus找不到mapper.xml的問題解決

    Springboot+mybatis plus找不到mapper.xml的問題解決

    本文主要介紹了Springboot+mybatis plus找不到mapper.xml的問題解決，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2023-05-05
  • Mybatis批量刪除數(shù)據(jù)操作方法

    Mybatis批量刪除數(shù)據(jù)操作方法

    MyBatis的作用我想不用多說,今天說說MyBatis中的批量刪除操作。 非常不錯，感興趣的朋友一起看看吧
    2016-09-09
  • Java生成驗證碼

    Java生成驗證碼

    本文介紹了Java生成驗證碼的流程與方法。具有很好的參考價值，下面跟著小編一起來看下吧
    2017-02-02
  • Java中Jedis基本使用

    Java中Jedis基本使用

    Redis的Java實現(xiàn)的客戶端，本文主要介紹了Java中Jedis基本使用，具有一定的參考價值，感興趣的小伙伴們可以參考一下
    2021-05-05
  • Java獲取磁盤空間的兩種代碼示例

    Java獲取磁盤空間的兩種代碼示例

    這篇文章主要介紹了Java獲取磁盤空間的兩種代碼示例，沒什么事的時候可以拿來玩玩，需要的朋友參考下。
    2017-11-11
  • Spring Boot集成Quartz注入Spring管理的類的方法

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

    本篇文章主要介紹了Spring Boot集成Quartz注入Spring管理的類的方法，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧
    2018-04-04
  • FasfDFS整合Java實現(xiàn)文件上傳下載功能實例詳解

    FasfDFS整合Java實現(xiàn)文件上傳下載功能實例詳解

    這篇文章主要介紹了FasfDFS整合Java實現(xiàn)文件上傳下載功能實例詳解,需要的朋友可以參考下
    2017-08-08
  • 解決spring cloud zuul與nginx的域名轉(zhuǎn)發(fā)問題

    解決spring cloud zuul與nginx的域名轉(zhuǎn)發(fā)問題

    這篇文章主要介紹了spring cloud zuul與nginx的域名轉(zhuǎn)發(fā)問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
    2021-07-07
  • springboot使用外置tomcat啟動方式

    springboot使用外置tomcat啟動方式

    這篇文章主要介紹了springboot使用外置tomcat啟動方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
    2021-11-11

最新評論