詳解Java如何實(shí)現(xiàn)小頂堆和大頂堆
大頂堆
每個(gè)結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)的值
小頂堆
每個(gè)結(jié)點(diǎn)的值都小于或等于其左右孩子結(jié)點(diǎn)的值
對(duì)比圖
實(shí)現(xiàn)代碼
public class HeapNode{ private int size;//堆大小 private int[] heap;//保存堆數(shù)組 //初始化堆 public HeapNode(int n) { heap = new int[n]; size = 0; } //小頂堆建堆 public void minInsert(int key){ int i = this.size; if (i==0) heap[0] = key; else { while (i>0 && heap[i/2]>key){ heap[i] = heap[i/2]; i = i/2; } heap[i] = key; } this.size++; } //大頂堆建堆 public void maxInsert(int key){ int i = this.size; if (i==0) heap[0] = key; else { while (i>0 && heap[i/2]<key){ heap[i] = heap[i/2]; i = i/2; } heap[i] = key; } this.size++; } //小頂堆刪除 public int minDelete(){ if (this.size==0) return -1; int top = heap[0]; int last = heap[this.size-1]; heap[0] = last; this.size--; //堆化 minHeapify(0); return top; } //大頂堆刪除 public int maxDelete(){ if (this.size==0) return -1; int top = heap[0]; int last = heap[this.size-1]; heap[0] = last; this.size--; //堆化 maxHeapify(0); return top; } //小頂堆化 public void minHeapify(int i){ int L = 2*i,R=2*i+1,min; if (L<=size && heap[L] < heap[i]) min = L; else min = i; if (R <= size && heap[R] < heap[min]) min = R; if (min!=i){ int t = heap[min]; heap[min] = heap[i]; heap[i] = t; minHeapify(min); } } //大頂堆化 public void maxHeapify(int i){ int L = 2*i,R=2*i+1,max; if (L<=size && heap[L] > heap[i]) max = L; else max = i; if (R <= size && heap[R] > heap[max]) max = R; if (max!=i){ int t = heap[max]; heap[max] = heap[i]; heap[i] = t; maxHeapify(max); } } //輸出堆 public void print(){ for (int i = 0; i < this.size; i++) { System.out.print(heap[i]+" "); } System.out.println(); } }
測(cè)試
public class Heap { static int[] a = {5,3,6,4,2,1}; static int n = a.length; public static void main(String[] args){ HeapNode heapNode = new HeapNode(n); for (int i = 0; i < n; i++) { heapNode.maxInsert(a[i]); } heapNode.print(); for (int i = 0; i < n; i++) { int min = heapNode.maxDelete(); System.out.print("堆頂:"+min+" 剩下堆元素:"); heapNode.print(); } } }
結(jié)果
到此這篇關(guān)于詳解Java如何實(shí)現(xiàn)小頂堆和大頂堆的文章就介紹到這了,更多相關(guān)Java實(shí)現(xiàn)小頂堆和大頂堆內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Java使用泛型實(shí)現(xiàn)棧結(jié)構(gòu)的示例代碼
泛型是JAVA重要的特性,使用泛型編程,可以使代碼復(fù)用率提高。本文將利用泛型實(shí)現(xiàn)簡(jiǎn)單的棧結(jié)構(gòu),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2022-08-08Java I/O深入學(xué)習(xí)之File和RandomAccessFile
這篇文章主要介紹了Java I/O深入學(xué)習(xí)之File和RandomAccessFile, I/O系統(tǒng)即輸入/輸出系統(tǒng),對(duì)于一門(mén)程序語(yǔ)言來(lái)說(shuō),創(chuàng)建一個(gè)好的輸入/輸出系統(tǒng)并非易事。在充分理解Java I/O系統(tǒng)以便正確地運(yùn)用之前,我們需要學(xué)習(xí)相當(dāng)數(shù)量的類。,需要的朋友可以參考下2019-06-06踩坑批量更新sql報(bào)錯(cuò),實(shí)際sql能夠正常執(zhí)行的問(wèn)題
在項(xiàng)目工程遷移過(guò)程中,遇到了一個(gè)批量更新接口在新工程中報(bào)錯(cuò)的問(wèn)題,通過(guò)分析,排除了代碼錯(cuò)誤的可能,最終發(fā)現(xiàn)是由于數(shù)據(jù)庫(kù)連接配置不當(dāng)導(dǎo)致的,在jdbc連接字符串中加入allowMultiQueries=true參數(shù)后,問(wèn)題得以解決,這個(gè)參數(shù)的作用是允許SQL批量執(zhí)行2022-12-12Spring Boot jar 啟動(dòng)時(shí)設(shè)置環(huán)境參數(shù)的操作
這篇文章主要介紹了Spring Boot jar 啟動(dòng)時(shí)設(shè)置環(huán)境參數(shù)的操作,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2021-06-06Java將日期類型Date時(shí)間戳轉(zhuǎn)換為MongoDB的時(shí)間類型數(shù)據(jù)
今天小編就為大家分享一篇關(guān)于Java將日期類型Date時(shí)間戳轉(zhuǎn)換為MongoDB的時(shí)間類型數(shù)據(jù),小編覺(jué)得內(nèi)容挺不錯(cuò)的,現(xiàn)在分享給大家,具有很好的參考價(jià)值,需要的朋友一起跟隨小編來(lái)看看吧2018-10-10Springboot輕量級(jí)的監(jiān)控組件SpringbootAdmin
這篇文章主要為大家介紹了Springboot輕量級(jí)的監(jiān)控組件SpringbootAdmin使用示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-02-02java算法實(shí)現(xiàn)紅黑樹(shù)完整代碼示例
這篇文章主要介紹了java算法實(shí)現(xiàn)紅黑樹(shù)完整代碼示例,具有一定參考價(jià)值,需要的朋友可以了解下。2017-11-11