二叉樹
在 Java 中,有許多不同類型的數據結構。堆基於稱為二叉樹的樹結構。二叉樹由節點組成,每個節點最多可以有 2 個子節點:

最大堆
最大堆(或maxheap)是一棵完全二叉樹。重要的是父節點的值必須大於或等於左子節點和右子節點的值。如果不遵守這一點,則您沒有最大堆。而最小堆則相反,根為最小值,連續節點的值遞增;每個子節點的值都大於或等於其父節點。也是完全二叉樹。最大堆的一個示例是:
優先隊列類
Java 中的堆可以使用PriorityQueue類來實現。PriorityQueues用於查找集合中最重要或最不重要的項目。可以在java.util.package中找到PriorityQueue類。PriorityQueues必須由可比較的對象組成,以便它們在隊列中按特定順序放置。PriorityQueue可以有一個比較器,以便在對象之間進行比較,並根據此比較形成隊列。一個例子是:import java.util.Comparator;
import java.util.PriorityQueue;
public class Main
{
public static void main(String[] args) {
// Create PriorityQueue with comparator for ascending order of array length
PriorityQueue intQueue = new PriorityQueue((a,b) -> a - b);
Integer [] array1 = {1, 2, 4, 6, 8, 9};
Integer [] array2 = {3, 6, 9};
Integer [] array3 = {2, 4, 8, 16, 32, 64, 128};
Integer [] array4 = {5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55};
Integer [] array5 = {4};
//Add the array lengths to intQueue
intQueue.add(array1.length);
intQueue.add(array2.length);
intQueue.add(array3.length);
intQueue.add(array4.length);
intQueue.add(array5.length);
//Write out contents of intQueue as stored
while (intQueue.size() != 0) {
System.out.println(intQueue.remove());
}
}
}
給出輸出:
1 3 6 7 11
在此示例中, intQueue 的默認大小為 11,因此沒有說明(通常是比較器之前的第一個參數)並且比較器已給出為:
(a,b) -> a - b
這將在intQueue 中的項目之間進行比較,並將其排序為升序排列的數組長度。
實現 PriorityQueue 創建最大堆
PriorityQueue類默認為沒有比較器的最小堆。最小堆與最大堆相反,因此根是最小值,後續子節點大於或等於根和後續父節點。因此,對於最大堆,有必要使用Java 的 Collections 框架中的reverseOrder()作為比較器。這將確保我們獲得最大堆而不是最小堆。此類具有有用的方法,例如add()、contains()、remove()、poll()和peek()。方法 | 描述 | 時間複雜度 |
---|---|---|
添加(J) | 在樹的末尾添加元素 J | O(LogN) |
移除(J) | 從樹中移除值 J | 在) |
輪詢() | 刪除樹的最大元素 | O(LogN) |
窺視() | 返回樹頂部的根元素 | O(1) |
包含(J) | 如果 J 在隊列中則返回 true,否則返回 false | 在) |

mport java.util.Collections;
import java.util.PriorityQueue;
public class MaxHeap {
public static void writeQueue(PriorityQueue<Integer> priorityQueue)
{
// Write out elements in queue, priorityQueue, and remove them using poll()
while(priorityQueue.size() != 0)
{
System.out.println(priorityQueue.poll());
}
}
public static void writeMaxHeap(PriorityQueue<Integer> priorityQueue)
{
// Write out elements in queue as a max heap - root, left child, right child, etc
for (Integer element : priorityQueue) {
System.out.println(element);
}
}
public static void main(String args[])
{
// Array of numbers to create a max heap array from
int[] theArray = {5, 3, 13, 10, 99, 19, 6, 51, 9};
// theQueue is created
PriorityQueue<Integer> theQueue =
new PriorityQueue<Integer>(Collections.reverseOrder());
// Elements are added to theQueue
for (int i = 0 ; i <theArray.length; ++i)
{
theQueue.add(theArray[i]);
}
// The head or root element (priority element) is printed out
System.out.println("The root value is : " + theQueue.peek());
// Find size of theQueue. Use method size()
Integer s = theQueue.size();
System.out.println("Size of theQueue? " + s);
// All elements of theQueue are printed in terms of parent,
// left child, right child
System.out.println("theQueue written using for loop:");
writeMaxHeap(theQueue);
// Does theQueue contain 10? Use method contains()
boolean b = theQueue.contains(10);
System.out.println("Does theQueue contain 10? " + b);
// Erasing value 10 from array using remove()
theQueue.remove(10);
// All elements of theQueue are printed out and removed.
// Each one is the maximum value left in the queue.
// At the end theQueue will be empty
System.out.println("theQueue written out using poll():");
writeQueue(theQueue);
// Find size of theQueue. Use method size()
s = theQueue.size();
System.out.println("Size of theQueue? " + s);
}
}
輸出:
99 隊列的大小?9 使用for循環編寫的theQueue 99 51 19 13 10 5 6 3 9 theQueue 是否包含 10?使用 poll() 寫出的 true theQueue 99 51 19 13 9 6 5 3 隊列的大小?0
最大堆積
Max Heapify 算法用於確保二叉樹是最大堆。如果我們在一個節點 n 處,它的子節點 left 和 right 本身也是最大堆,那麼很好,我們有一個最大堆。如果整個樹都不是這種情況,那麼我們就沒有最大堆。Max Heapify 算法用於對樹進行排序,使其遵循最大堆原則。Max Heapify 僅適用於一個節點。如果要求數組是最大堆數組,那麼所有的子樹都必須在根之前轉換為最大堆,一次一個。該算法必須在每個節點上使用。這將在 N/2 個節點上完成(葉子將遵守最大堆要求)。堆的時間複雜度是O(NlogN),對於一個高度為X的節點,時間複雜度是O(X)。下面的代碼顯示瞭如何 maxheapify 一棵樹(一個數組)。public class MaxHeapify
{
public static Integer[] maxHeapify(Integer[ ] array, Integer i)
{
// Create left-child and right-child for the node in question
Integer leftChild = 2 * i + 1;
Integer rightChild = 2 * i + 2;
// Assign maxVal to parent node, i
Integer maxVal = i;
// Set maxVal to greater of the two: node or left-child
if( leftChild < array.length && array[leftChild] > array[maxVal] )
maxVal = leftChild;
// Set maxVal to greater of the two: maxVal or right-child
if( rightChild < array.length && array[rightChild] > array[maxVal] )
maxVal = rightChild;
// Check if maxVal is not equal to parent node, then set parent node to
// maxVal, swap values and then do a maxheapify on maxVal
// which is now the previous parent node
if( maxVal != i )
{
Integer value = array[i];
array[i] = array[maxVal];
array[maxVal] = value;
array = maxHeapify(array, maxVal);
}
return array;
}
public static Integer[] maxHeapCreate(Integer array[])
{
// Call maxHeapify to arrange array in a max heap
Integer [] theNewArr = array;
for( Integer i = array.length/2; i >= 0; i-- )
theNewArr = maxHeapify(array, i);
return theNewArr;
}
public static void main(String[] args)
{
// Create array to be maxheapified, theArray,
// and array, newArray, to write results into, by calling maxheapCreate
// newArray will now be a maxheap
Integer[] theArray = {5, 3, 13, 10, 99, 19, 6, 51, 9};
Integer[ ] newArray = maxHeapCreate(theArray);
// Print out contents of newArray
System.out.println("newArray:");
for(int i = 0; i < newArray.length; ++i)
{
System.out.println(newArray[i]);
}
// Print out labelled contents of newArray
System.out.println(" root : " + newArray[0]);
for (int i = 0; i <= newArray.length/2 - 1; i++) {
System.out.print(" parent node : " + newArray[i] + " left child : " +
newArray[(2*i)+1] + " right child :" + newArray[(2*i)+2]);
System.out.println();
}
}
}
給出輸出:
新數組:99 51 19 10 3 13 65 9根:99個父節點:99個左子節點:51個右子節點:19個父節點:51個左子節點:10個右子節點:3個父節點:19個左子節點:13個右子節點:6個父節點:10個左子節點:5個右節點孩子:999999999 父節點:99 左子節點:51 右子節點:19 父節點:51 左子節點:10 右子節點:3 父節點:19 左子節點:13 右子節點:6 父節點:10 左子節點:5 右子節點:999 父節點:99 左子節點:51 右子節點:19 父節點:51 左子節點:10 右子節點:3 父節點:19 左子節點:13 右子節點:6 父節點:10 左子節點:5 右子節點:96 父節點:10 左子節點:5 右子節點:96 父節點:10 左子節點:5 右子節點:9
在此代碼中,創建了theArray並用數字填充。創建第二個數組newArray,這次它將包含方法maxheapCreate的結果,即最大堆數組。方法maxHeapCreate從main調用,這裡創建了一個新數組theNewArr並用maxHeapify結果填充。這是通過循環輸入數組大小的一半來完成的。對於循環的每次傳遞,調用方法maxHeapify從數組中間的元素開始並以第一個元素結束。對於maxHeapify的每次調用,找到父節點 i 的左孩子和右孩子,並進行檢查以找出三者中最大的一個,將其定義為maxVal。如果maxVal不等於父節點,則進行交換,以便交換父節點和maxVal,然後這次在maxVal上再次調用maxHeapify,並執行與之前相同的步驟。最終將創建最大堆,並且將不再執行迭代。更新後的數組 array現在作為newArray返回到main ,然後將每個連續的元素打印到控制台。新數組現在是最大堆。請注意,在前面使用PriorityQueue 的示例中,數字被寫出:根,根的右子作為父,根的左子作為父,第一個右子的右子作為父,第一個的左子左孩子作為父母,第一個左孩子的右孩子作為父母,第一個右孩子的左孩子作為父母,等等。它們的順序與使用PriorityQueue時的順序略有不同,因為比較是在連續元素之間進行的而在 maxheapify 示例中,節點與數組中接下來的兩個連續元素進行比較,並交換最大值。簡而言之,使用了兩種不同的算法。兩者都創建一個最大堆。
GO TO FULL VERSION