Java 中的最大堆

二叉树

在 Java 中，有许多不同类型的数据结构。堆基于称为二叉树的树结构。二叉树由节点组成，每个节点最多可以有 2 个子节点：二叉树由一个父节点组成，父节点可以有 0 到 2 个节点。它可以有一个左子节点和/或一个右子节点，或者根本没有节点。在一棵完全二叉树中，除了最后一层可以满，但不需要满，所有节点都被填满。最后一层，即第 n 层，可以有 1 到 2n 个节点，其中第一个节点在 n = 0 处并且是根。

最大堆

最大堆（或maxheap）是一棵完全二叉树。重要的是父节点的值必须大于或等于左子节点和右子节点的值。如果不遵守这一点，则您没有最大堆。而最小堆则相反，根为最小值，连续节点的值递增；每个子节点的值都大于或等于其父节点。也是完全二叉树。最大堆的一个示例是：最大堆可以从数组构建。这个数组将被认为是一棵树。对于堆，如果根（树的顶部父节点）存储在位置（索引）n，则为数组theArray定义为theArray[n]. 因此，左子节点和右子节点分别位于theArray[2n+1]和theArray[2n+2]处。对于最大堆，根位于theArray[0]处。对于n层，root n = 0： theArr[n]是父节点 theArr[(2*n)+1]是左子节点 theArr[(2*n)+2]是右子节点

优先队列类

Java 中的堆可以使用PriorityQueue类来实现。PriorityQueue用于查找集合中最重要或最不重要的项目。可以在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());
        }
    }          
}

给出输出： 在此示例中， intQueue 的默认大小为 11，因此没有说明（通常是比较器之前的第一个参数）并且比较器已给出为： 这将在intQueue 中的项目之间进行比较，并将其排序为升序排列的数组长度。

实现 PriorityQueue 创建最大堆

PriorityQueue类默认为没有比较器的最小堆。最小堆与最大堆相反，因此根是最小值，后续子节点大于或等于根和后续父节点。因此，对于最大堆，有必要使用Java 的 Collections 框架中的reverseOrder()作为比较器。这将确保我们获得最大堆而不是最小堆。此类具有有用的方法，例如add()、contains()、remove()、poll()和peek()。 元素被添加到队列中并且可以按任何顺序排列。新的 PriorityQueue 队列将这些元素以相反的顺序存储为最大堆。当队列被写出时，顺序将是： Root Left-child with root as parent (Left-child_1) Right-child with root as parent (Right-child_1) Left-child with Left-child_1 parent (Left-child_2 ) Right-child with Left-child_1 as parent (Right-child_2) Left-child with Right-child_1 as parent (Left-child_3) Right-child with Right-child_1 as parent (Right-child_3) Left-child with Left-child_2作为父母 (Left-child_4) Right-child with Left-child_2 作为父母 (Right-child_4) 等下面的代码是java中如何创建最大堆（maxheap）的一个例子。要做的第一件事是用将为其创建最大堆的值填充一个数组。这称为theArray。接下来，创建一个PriorityQueue theQueue ，然后将theArray中的元素添加到其中。这使用方法add()，例如theQueue.add(10)将 10 添加到队列的末尾。为了说明PriorityQueue类的一些功能，然后使用方法peek()查找堆头，这是最大值，在本例中为 99。下一个任务是检查堆的大小使用尺寸（）发现它是 9 并将其打印到控制台。writeMaxHeap方法按照根顺序写出队列中的元素，以根为父的左子，以根为父的右子，以第一个左子为父的左子，以第一个左子为右子的右子parent, right-child with first right-child as parent, left-child with first right-child as parent etc, 随后的值使用左右孩子作为父母，顺序与上述相同。 PriorityQueue方法contains(J)用于查找特定元素 J 是否在队列中。在本例中，我们寻找 J = 10。在我们的示例中，它确实在队列中，因此它被写入控制台为真。然后使用另一个PriorityQueue方法remove(J)从theQueue中删除 J = 10 。为了说明PriorityQueue的更多功能，方法poll()用于使用while循环删除头元素（最大值），每次删除新队列中的头元素，每次都将队列大小减一。这发生在方法writeQueue中从主要调用。每次删除的元素都会打印到控制台。原始队列最终将没有任何元素。打印的元素是按值降序排列的最大堆，每次都打印出队列的头部。

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);
       }
   }

输出：

最大堆积

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

给出输出： 在此代码中，创建了theArray并用数字填充。创建第二个数组newArray，这次它将包含方法的结果maxheapCreate，即最大堆数组。方法maxHeapCreate从main调用，这里创建了一个新数组theNewArr并用maxHeapify结果填充。这是通过循环输入数组大小的一半来完成的。对于循环的每次传递，调用方法maxHeapify从数组中间的元素开始并以第一个元素结束。对于maxHeapify的每次调用，找到父节点 i 的左孩子和右孩子，并进行检查以找出三者中最大的一个，将其定义为maxVal。如果maxVal不等于父节点，则进行交换，以便交换父节点和maxVal ，然后这次在maxVal上再次调用maxHeapify，并执行与之前相同的步骤。最终将创建最大堆，并且将不再执行迭代。更新后的数组 array现在作为newArray返回到main ，然后将每个连续的元素打印到控制台。新数组现在是最大堆。请注意，在前面使用PriorityQueue 的示例中，数字被写出：根，根的右子作为父，根的左子作为父，第一个右子的右子作为父，第一个的左子左孩子作为父母，第一个左孩子的右孩子作为父母，第一个右孩子的左孩子作为父母，等等。它们的顺序与使用PriorityQueue时的顺序略有不同，因为比较是在连续元素之间进行的而在 maxheapify 示例中，节点与数组中接下来的两个连续元素进行比较，并交换最大值。简而言之，使用了两种不同的算法。两者都创建一个最大堆。

结论

所以在这里我们已经了解了最大堆以及如何使用PriorityQueue或 Max Heapify 算法创建它。将PriorityQueue与reverseOrder()结合使用是一种巧妙的方法，也是推荐的方法。但是，您可以研究这些示例并编写自己的方法，因为这将是一个很好的编码练习，可以帮助您在 Java Junior 面试中取得成功。