CodeGym /Java Blog /Toto sisi /Java 中的最大堆
John Squirrels

San Francisco

# Java 中的最大堆

## 優先隊列類

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
//Write out contents of intQueue as stored
while (intQueue.size() != 0) {
System.out.println(intQueue.remove());
}
}
}
``````

1 3 6 7 11

(a,b) -> a - b

## 實現 PriorityQueue 創建最大堆

``````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)
{
}

// 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();
}
}
}``````

## 結論

TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION