深入了解Java數(shù)據(jù)結(jié)構(gòu)和算法之堆
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)容!
- Java數(shù)據(jù)結(jié)構(gòu)之優(yōu)先級(jí)隊(duì)列(堆)圖文詳解
- Java 數(shù)據(jù)結(jié)構(gòu)與算法系列精講之二叉堆
- Java深入了解數(shù)據(jù)結(jié)構(gòu)之優(yōu)先級(jí)隊(duì)列(堆)
- Java數(shù)據(jù)結(jié)構(gòu)中堆的向下和向上調(diào)整解析
- Java 數(shù)據(jù)結(jié)構(gòu)之堆的概念與應(yīng)用
- java數(shù)據(jù)結(jié)構(gòu)-堆實(shí)現(xiàn)優(yōu)先隊(duì)列
- java 數(shù)據(jù)結(jié)構(gòu)之堆排序(HeapSort)詳解及實(shí)例
- Java?超詳細(xì)講解數(shù)據(jù)結(jié)構(gòu)中的堆的應(yīng)用
相關(guān)文章
Spring事務(wù)注解@Transactional失效的八種場(chǎng)景分析
最近在開發(fā)采用Spring框架的項(xiàng)目中,使用了@Transactional注解,但發(fā)現(xiàn)事務(wù)注解失效了,所以這篇文章主要給大家介紹了關(guān)于Spring事務(wù)注解@Transactional失效的八種場(chǎng)景,需要的朋友可以參考下2021-05-05

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

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

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

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

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