Java堆&優(yōu)先級隊列示例講解(上)
更新時間：2022年03月18日 11:24:47 作者：愛干飯的猿
這篇文章主要通過示例詳細為大家介紹Java中的堆以及優(yōu)先級隊列，文中的示例代碼講解詳細，對我們了解java有一定幫助，需要的可以參考一下
1. 二叉樹的順序存儲
1.1 存儲方式
使用數(shù)組保存二叉樹結構，方式即將二叉樹用 層序遍歷 方式放入數(shù)組中。
一般只適合表示完全二叉樹，這種方式的主要用法就是堆的表示。
因為非完全二叉樹會有空間的浪費（所有非完全二叉樹用鏈式存儲）。
1.2 下標關系
已知雙親 (parent) 的下標，則：
左孩子 (left) 下標 = 2 * parent + 1;
右孩子 (right) 下標 = 2 * parent + 2;
已知孩子（不區(qū)分左右） (child) 下標，則：
雙親 (parent) 下標 = (child - 1) / 2;
2. 堆(heap)
2.1 概念
1. 堆邏輯上是一棵完全二叉樹
2. 堆物理上是保存在數(shù)組中
3. 滿足任意結點的值都大于其子樹中結點的值，叫做大堆，或者大根堆，或者最大堆
4. 反之，則是小堆，或者小根堆，或者最小堆
5. 堆的基本作用是，快速找集合中的 最值
2.2 操作-（下沉&上浮）本例是最大堆
元素下沉：
/**
* 下沉操作
*/
public void siftDown(int k){
//還存在子樹
while (leftChild(k) < data.size()){
int j = leftChild(k);
//判斷是否存在右子樹且大于左子樹的值
if(j+1 < data.size() && data.get(j+1) > data.get(j)){
j=j+1;
}
//此時j為左右子樹最大值
//和當前節(jié)點比較大小
if(data.get(j) <= data.get(k)){
break;
}else {
swap(k,j);
k=j;
}
}
}
元素上?。?/p>
/**
* 上浮操作
*/
// 上浮操作的終止條件: 已經(jīng)走到根節(jié)點 || 當前節(jié)點值 <= 父節(jié)點值
// 循環(huán)的迭代條件 : 還存在父節(jié)點并且當前節(jié)點值 > 父節(jié)點值
private void siftUp(int k) {
while (k>0 && data.get(k)>data.get(parent(k))){
swap(k,parent(k));
k=parent(k);
}
}
其中swap方法是交換操作：
//交換三連
private void swap(int i,int j) {
int temp = data.get(j);
data.set(j,data.get(i));
data.set(i,temp);
}
堆化數(shù)組：
/**
* 將任意數(shù)組堆化
* @param arr
*/
public MaxHeap(int[] arr){
data = new ArrayList<>(arr.length);
// 1.先將arr的所有元素復制到data數(shù)組中
for(int i : arr){
data.add(i);
}
// 2.從最后一個非葉子結點開始進行siftDown
for (int i = parent(data.size()-1); i >=0 ; i--) {
siftDown(i);
}
}
圖示：
以此數(shù)組為例：
// 調(diào)整前
int[] array = { 27,15,19,18,28,34,65,49,25,37 };
// 調(diào)整后
int[] array = { 15,18,19,25,28,34,65,49,27,37 };
時間復雜度分析：
最壞的情況即圖示的情況，從根一路比較到葉子，比較的次數(shù)為完全二叉樹的高度
即時間復雜度為 O(log(n))
2.3 建堆-完整代碼（最大堆）
/**
* 基于整形最大堆實現(xiàn)
* 時根節(jié)點從0開始編號,若此時節(jié)點編號為k
* 左孩子為2k+1
* 右孩子為2k+2
* 父節(jié)點為（k-1）/2
*/
import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;
public class MaxHeap {
// 使用JDK的動態(tài)數(shù)組(ArrayList)來存儲一個最大堆
List<Integer> data;
// 構造方法的this調(diào)用
public MaxHeap(){
this(10);
}
// 初始化的堆大小
public MaxHeap(int size){
data = new ArrayList<>(size);
}
/**
* 將任意數(shù)組堆化
* @param arr
*/
public MaxHeap(int[] arr){
data = new ArrayList<>(arr.length);
// 1.先將arr的所有元素復制到data數(shù)組中
for(int i : arr){
data.add(i);
}
// 2.從最后一個非葉子結點開始進行siftDown
for (int i = parent(data.size()-1); i >=0 ; i--) {
siftDown(i);
}
}
/**
* 向最大堆中增加值為Value的元素
* @param value
*/
public void add(int value){
//1.先直接加到堆的末尾
data.add(value);
//2.元素上浮操作
siftUp(data.size()-1);
}
/**
* 只找到堆頂元素值
* @return
*/
public int peekMax (){
if(isEmpty()){
throw new NoSuchElementException("heap is empty!connot peek");
}
return data.get(0);
}
/**
* 取出當前最大堆的最大值
*/
public int extractMax(){
// 取值一定注意判空
if(isEmpty()){
throw new NoSuchElementException("heap is empty!connot extract");
}
int max = data.get(0);
// 1.將數(shù)組末尾元素頂?shù)蕉秧?
int lastValue =data.get(data.size()-1);
data.set(0,lastValue);
// 2.將數(shù)組末尾的元素刪除
data.remove(data.size()-1);
// 3.進行元素的下沉操作
siftDown(0);
return max;
}
/**
* 下沉操作
*/
public void siftDown(int k){
//還存在子樹
while (leftChild(k) < data.size()){
int j = leftChild(k);
//判斷是否存在右子樹且大于左子樹的值
if(j+1 < data.size() && data.get(j+1) > data.get(j)){
j=j+1;
}
//此時j為左右子樹最大值
//和當前節(jié)點比較大小
if(data.get(j) <= data.get(k)){
break;
}else {
swap(k,j);
k=j;
}
}
}
/**
* 上浮操作
*/
// 上浮操作的終止條件: 已經(jīng)走到根節(jié)點 || 當前節(jié)點值 <= 父節(jié)點值
// 循環(huán)的迭代條件 : 還存在父節(jié)點并且當前節(jié)點值 > 父節(jié)點值
private void siftUp(int k) {
while (k>0 && data.get(k)>data.get(parent(k))){
swap(k,parent(k));
k=parent(k);
}
}
//交換三連
private void swap(int i,int j) {
int temp = data.get(j);
data.set(j,data.get(i));
data.set(i,temp);
}
//判讀堆為空
public boolean isEmpty(){
return data.size() == 0;
}
//根據(jù)索引找父節(jié)點
public int parent(int k){
return (k-1)>>1;
}
//根據(jù)索引找左孩子
public int leftChild(int k){
return k<<2+1;
}
//根據(jù)索引找右孩子
public int rightChild(int k){
return k<<2+2;
}
@Override
public String toString() {
return data.toString();
}
}
ps:隨機數(shù)操作
int[] data=new int[10000];
//隨機數(shù)
ThreadLocalRandom random = ThreadLocalRandom.current();
for (int i = 0; i < data.length; i++) {
data[i] = random.nextInt();
}
3. 優(yōu)先級隊列
詳見下節(jié)：Java堆&優(yōu)先級隊列示例講解(下)
到此這篇關于Java堆&優(yōu)先級隊列示例講解(上)的文章就介紹到這了,更多相關Java 堆 優(yōu)先級隊列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了Springboot使用logback的注意事項，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-07-07
本篇總結的是Spring MVC框架相關的面試題，后續(xù)會持續(xù)更新，希望我的分享可以幫助到正在備戰(zhàn)面試的實習生或者已經(jīng)工作的同行，如果發(fā)現(xiàn)錯誤還望大家多多包涵，不吝賜教，謝謝2021-07-07
這篇文章主要介紹了利用MyBatis進行不同條件的like模糊查詢,小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2018-08-08
這篇文章主要介紹了Springboot常用注解及作用說明,Springboot開發(fā)中注解是非常重要的不可或缺的,那么Springboot中有哪些常用的注解呢,今天我們就來看一下這些注解和其作用,需要的朋友可以參考下2023-08-08
使用@Validated 和 BindingResult 遇到的坑及解決
這篇文章主要介紹了使用@Validated 和 BindingResult 遇到的坑及解決方案，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-10-10
Java Object類詳解_動力節(jié)點Java學院整理
Java作為一個龐大的知識體系，涉及到的知識點繁多，本文將從Java中最基本的類java.lang.Object開始談起，對java object類相關知識感興趣的朋友一起學習吧2017-04-04
下面小編就為大家?guī)硪黄狫ava文件(io)編程_文件字節(jié)流的使用方法。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-08-08
SpringMVC 重新定向redirect請求中攜帶數(shù)據(jù)方式
這篇文章主要介紹了SpringMVC 重新定向redirect請求中攜帶數(shù)據(jù)方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-12-12
這篇文章主要為大家介紹了Java 程序里transient關鍵字使用方法示例,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-11-11
在java中使用SPI創(chuàng)建可擴展的應用程序操作
這篇文章主要介紹了在java中使用SPI創(chuàng)建可擴展的應用程序操作，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-09-09