Java實(shí)現(xiàn)二叉堆、大頂堆和小頂堆
什么是二叉堆
二叉堆就是完全二叉樹(shù)，或者是靠近完全二叉樹(shù)結(jié)構(gòu)的二叉樹(shù)。在二叉樹(shù)建樹(shù)時(shí)采取前序建樹(shù)就是建立的完全二叉樹(shù)。也就是二叉堆。所以二叉堆的建堆過(guò)程理論上講和前序建樹(shù)一樣。
什么是大頂堆、小頂堆
二叉堆本質(zhì)上是一棵近完全的二叉樹(shù)，那么大頂堆和小頂堆必然也是滿足這個(gè)結(jié)構(gòu)要求的。在此之上，大頂堆要求對(duì)于一個(gè)節(jié)點(diǎn)來(lái)說(shuō)，它的左右節(jié)點(diǎn)都比它小；小頂堆要求對(duì)于一個(gè)節(jié)點(diǎn)來(lái)說(shuō)，它的左右節(jié)點(diǎn)都比它大。
建堆
二叉堆建堆本質(zhì)上和前序建堆差不多，只不過(guò)需要考慮的一點(diǎn)就是大小關(guān)系，這一點(diǎn)和二叉搜索樹(shù)建樹(shù)有點(diǎn)相似，所以可以得出結(jié)論，建樹(shù)，本質(zhì)上都是遞歸建樹(shù)，只不過(guò)因?yàn)閿?shù)據(jù)結(jié)構(gòu)的大小要求不一樣，需要的判斷函數(shù)不一樣，節(jié)點(diǎn)進(jìn)入哪個(gè)位置也不一樣。
大頂堆和小頂堆也分為穩(wěn)定和不穩(wěn)定的堆。穩(wěn)定和不穩(wěn)定指如果具備相同的值，那么他們的插入順序應(yīng)該和節(jié)點(diǎn)順序一致。
程序?qū)崿F(xiàn)
首先，定義出基本的堆結(jié)構(gòu)
public class BinaryHeap {
? ? private Integer value;
? ? private BinaryHeap leftChild;
? ? private BinaryHeap rightChild;
}建堆過(guò)程與建二叉樹(shù)過(guò)程一致
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é)點(diǎn)兩種都不為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é)點(diǎn)的左節(jié)點(diǎn)為空，則把當(dāng)前值放到左節(jié)點(diǎn)，如果左節(jié)點(diǎn)不為空，右節(jié)點(diǎn)為空，則把值放到右節(jié)點(diǎn)。如果左右節(jié)點(diǎn)都不為空，就將建樹(shù)過(guò)程轉(zhuǎn)移到下一層，如果左節(jié)點(diǎn)有為空的子節(jié)點(diǎn)，就轉(zhuǎn)移給左節(jié)點(diǎn)，如果左節(jié)點(diǎn)沒(méi)有為空的子節(jié)點(diǎn)，且右節(jié)點(diǎn)有為空的子節(jié)點(diǎn)，那么轉(zhuǎn)移給右節(jié)點(diǎn)。如果左右節(jié)點(diǎn)都沒(méi)有為空的子節(jié)點(diǎn)，那么也轉(zhuǎn)移給左節(jié)點(diǎn)。
以序列2,3,4,5,9,6,8,7為例，按照該算法建立出來(lái)的二叉堆結(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ǔ)上，有一個(gè)要求，根節(jié)點(diǎn)比左右子樹(shù)的任何節(jié)點(diǎn)的值都大。那么建樹(shù)的過(guò)程可以分為兩步，對(duì)于每一個(gè)值，首先按照建樹(shù)過(guò)程，會(huì)到二叉堆的最底部，然后通過(guò)不斷的讓自己與自己的根節(jié)點(diǎn)做比較，如果自己大于根節(jié)點(diǎn)，就交換自己與根節(jié)點(diǎn)的位置，遞歸回溯即可。
邏輯過(guò)程
假設(shè)現(xiàn)在紅色節(jié)點(diǎn)組成的已經(jīng)是一個(gè)大頂堆，現(xiàn)在新增了一個(gè)節(jié)點(diǎn)到這個(gè)二叉堆中，而且是比任意節(jié)點(diǎn)都大，那么黑色箭頭將是該節(jié)點(diǎn)的行動(dòng)路線，它會(huì)反復(fù)與父級(jí)比較，如果大于父級(jí)，則交換和父級(jí)的關(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;
}
該方法放在普通建樹(shù)方法之后，就是大頂堆的建樹(shù)方法了，總的方法如下：
public static BinaryHeap bigPush(BinaryHeap binaryHeap, Integer value) {
binaryHeap = buildHeap(binaryHeap, value);
up(binaryHeap);
return binaryHeap;
}
還是以序列2,3,4,5,9,6,8,7為例，按照該算法建立出來(lái)的大頂堆結(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
}
}
}
建立小頂堆
小頂堆與大頂堆類似
邏輯過(guò)程
過(guò)程與大頂堆一致，不過(guò)此時(shí)是比父級(jí)小就和父級(jí)交換。
程序?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;
}
這個(gè)是向下走的過(guò)程，最終代碼為：
public static BinaryHeap smallPush(BinaryHeap binaryHeap, Integer value) {
binaryHeap = buildHeap(binaryHeap, value);
down(binaryHeap);
return binaryHeap;
}
以序列2,3,4,5,9,6,8,7為例，按照該算法建立出來(lái)的小頂堆結(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;
}
取出來(lái)之后，需要重新調(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實(shí)現(xiàn)二叉堆、大頂堆和小頂堆的文章就介紹到這了,更多相關(guān)Java內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
maven創(chuàng)建spark項(xiàng)目的pom.xml文件配置demo
這篇文章主要為大家介紹了maven創(chuàng)建spark項(xiàng)目的pom.xml文件配置demo，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-05-05
OSS的英文全稱是Object?Storage?Service,翻譯成中文就是對(duì)象存儲(chǔ)服務(wù),官方一點(diǎn)解釋就是對(duì)象存儲(chǔ)是一種使用HTTP?API存儲(chǔ)和檢索非結(jié)構(gòu)化數(shù)據(jù)和元數(shù)據(jù)對(duì)象的工具,本文給大家詳細(xì)介紹了SpringBoot集成七牛云OSS的示例,需要的朋友可以參考下2023-11-11
Spring Boot與Spring Security的跨域問(wèn)題解決方案
跨域問(wèn)題是指在Web開(kāi)發(fā)中,瀏覽器出于安全考慮,限制了不同域名之間的資源訪問(wèn),本文重點(diǎn)給大家介紹Spring Boot與Spring Security的跨域問(wèn)題解決方案,感興趣的朋友一起看看吧2023-09-09
詳解SpringBoot與SpringCloud的版本對(duì)應(yīng)詳細(xì)版
這篇文章主要介紹了詳解SpringBoot與SpringCloud的版本對(duì)應(yīng)詳細(xì)版，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-09-09
Java同樣也提供了拋出異常、捕捉異常和finally語(yǔ)句的使用來(lái)處理程序異常,下面就來(lái)具體看一下Java中的異常處理用法及其架構(gòu)和使用建議:2016-06-06
微服務(wù)分布式架構(gòu)實(shí)現(xiàn)日志鏈路跟蹤的方法
在現(xiàn)有的系統(tǒng)中，由于大量的其他用戶/其他線程的日志也一起輸出穿行其中導(dǎo)致很難篩選出指定請(qǐng)求的全部相關(guān)日志。那我們?nèi)绾蝸?lái)處理呢？帶著這個(gè)問(wèn)題一起通過(guò)本文學(xué)習(xí)下吧2021-08-08
MyBatisPlus?TypeHandler自定義字段類型轉(zhuǎn)換Handler
這篇文章主要為大家介紹了MyBatisPlus?TypeHandler自定義字段類型轉(zhuǎn)換Handler示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-08-08
使用 Spring Boot 2.0 + WebFlux 實(shí)現(xiàn) RESTful API功能
什么是 Spring WebFlux, 它是一種異步的, 非阻塞的, 支持背壓(Back pressure)機(jī)制的Web 開(kāi)發(fā)框架.下面通過(guò)本文給大家介紹使用 Spring Boot 2.0 + WebFlux 實(shí)現(xiàn) RESTful API功能，需要的朋友參考下吧2018-01-01
本文主要介紹了JVM堆和棧的區(qū)別。具有很好的參考價(jià)值，下面跟著小編一起來(lái)看下吧2017-02-02
java導(dǎo)出數(shù)據(jù)庫(kù)中Excel表格數(shù)據(jù)的方法
這篇文章主要為大家詳細(xì)介紹了java導(dǎo)出數(shù)據(jù)庫(kù)中Excel表格數(shù)據(jù)的方法，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-08-08