Montón máximo en Java

Un max-heap es un árbol binario completo en el que el valor de cada Node interno es mayor o igual que los valores de los elementos secundarios de ese Node. Asignar los elementos de un montón a una array es trivial: si un Node se almacena en un índice k, entonces su hijo izquierdo se almacena en el índice 2k + 1 y su hijo derecho en el índice 2k + 2.

Ilustración: montón máximo 

¿Cómo se representa Max Heap? 

A-Max Heap es un árbol binario completo. El montón A-Max generalmente se representa como una array. El elemento raíz estará en Arr[0]. La siguiente tabla muestra los índices de otros Nodes para el i-ésimo Node, es decir, Arr[i]: 

Arr[(i-1)/2] Devuelve el Node padre. 
Arr[(2*i)+1] Devuelve el Node secundario izquierdo. 
Arr[(2*i)+2] Devuelve el Node secundario correcto.

Las operaciones en Max Heap son las siguientes:

• getMax(): Devuelve el elemento raíz de Max Heap. La complejidad temporal de esta operación es O(1) .
• extractMax(): elimina el elemento máximo de MaxHeap . La Complejidad de Tiempo de esta Operación es O(Log n) ya que esta operación necesita mantener la propiedad del montón llamando al método heapify() después de eliminar la raíz.
•  insert(): Insertar una nueva clave toma tiempo O (Log n) . Agregamos una nueva clave al final del árbol. Si la nueva clave es más pequeña que su padre, entonces no necesitamos hacer nada. De lo contrario, debemos recorrer hacia arriba para corregir la propiedad del montón violada.

Nota: En la implementación a continuación, indexamos desde el índice 1 para simplificar la implementación. 

Métodos: 

Hay 2 métodos por los cuales podemos lograr el objetivo como se indica: 

1. Enfoque básico mediante la creación del método maxHeapify()
2. Usando el método Collections.reverseOrder() a través de funciones de biblioteca

Método 1: enfoque básico mediante la creación del método maxHeapify()

Crearemos un método asumiendo que los subárboles izquierdo y derecho ya están acumulados, solo necesitamos arreglar la raíz.

Ejemplo

// Java program to implement Max Heap
 
// Main class
public class MaxHeap {
    private int[] Heap;
    private int size;
    private int maxsize;
 
    // Constructor to initialize an
    // empty max heap with given maximum
    // capacity
    public MaxHeap(int maxsize)
    {
        // This keyword refers to current instance itself
        this.maxsize = maxsize;
        this.size = 0;
        Heap = new int[this.maxsize];
    }
 
    // Method 1
    // Returning position of parent
    private int parent(int pos) { return (pos - 1) / 2; }
 
    // Method 2
    // Returning left children
    private int leftChild(int pos) { return (2 * pos) + 1; }
 
    // Method 3
    // Returning right children
    private int rightChild(int pos){ return (2 * pos) + 2; }
 
    // Method 4
    // Returning true of given node is leaf
    private boolean isLeaf(int pos)
    {
        if (pos > (size / 2) && pos <= size) {
            return true;
        }
        return false;
    }
 
    // Method 5
    // Swapping nodes
    private void swap(int fpos, int spos)
    {
        int tmp;
        tmp = Heap[fpos];
        Heap[fpos] = Heap[spos];
        Heap[spos] = tmp;
    }
 
    // Method 6
    // Recursive function to max heapify given subtree
    private void maxHeapify(int pos)
    {
        if (isLeaf(pos))
            return;
 
        if (Heap[pos] < Heap[leftChild(pos)]
            || Heap[pos] < Heap[rightChild(pos)]) {
 
            if (Heap[leftChild(pos)]
                > Heap[rightChild(pos)]) {
                swap(pos, leftChild(pos));
                maxHeapify(leftChild(pos));
            }
            else {
                swap(pos, rightChild(pos));
                maxHeapify(rightChild(pos));
            }
        }
    }
 
    // Method 7
    // Inserts a new element to max heap
    public void insert(int element)
    {
        Heap[size] = element;
 
        // Traverse up and fix violated property
        int current = size;
        while (Heap[current] > Heap[parent(current)]) {
            swap(current, parent(current));
            current = parent(current);
        }
        size++;
    }
 
    // Method 8
    // To display heap
    public void print()
    {
       
      for(int i=0;i<size/2;i++){
 
            System.out.print("Parent Node : " + Heap[i] );
             
            if(leftChild(i)<size) //if the child is out of the bound of the array
               System.out.print( " Left Child Node: " + Heap[leftChild(i)]);
             
            if(rightChild(i)<size) //if the right child index must not be out of the index of the array
                System.out.print(" Right Child Node: "+ Heap[rightChild(i)]);
             
                System.out.println(); //for new line
             
        }
           
    }
 
    // Method 9
    // Remove an element from max heap
    public int extractMax()
    {
        int popped = Heap[0];
        Heap[0] = Heap[--size];
        maxHeapify(0);
        return popped;
    }
 
    // Method 10
    // main dri er method
    public static void main(String[] arg)
    {
        // Display message for better readability
        System.out.println("The Max Heap is ");
 
        MaxHeap maxHeap = new MaxHeap(15);
 
        // Inserting nodes
        // Custom inputs
        maxHeap.insert(5);
        maxHeap.insert(3);
        maxHeap.insert(17);
        maxHeap.insert(10);
        maxHeap.insert(84);
        maxHeap.insert(19);
        maxHeap.insert(6);
        maxHeap.insert(22);
        maxHeap.insert(9);
 
        // Calling maxHeap() as defined above
        maxHeap.print();
 
        // Print and display the maximum value in heap
        System.out.println("The max val is "
                           + maxHeap.extractMax());
    }
}

The Max Heap is 
Parent Node : 84 Left Child Node: 22 Right Child Node: 19
Parent Node : 22 Left Child Node: 17 Right Child Node: 10
Parent Node : 19 Left Child Node: 5 Right Child Node: 6
Parent Node : 17 Left Child Node: 3 Right Child Node: 9
The max val is 84

Método 2: usar el método Collections.reverseOrder() a través de funciones de biblioteca 

Usamos la clase PriorityQueue para implementar Heaps en Java. Esta clase implementa Min Heap de forma predeterminada. Para implementar Max Heap, usamos el método  Collections.reverseOrder() .

Ejemplo 

// Java program to demonstrate working
// of PriorityQueue as a Max Heap
// Using Collections.reverseOrder() method
 
// Importing all utility classes
import java.util.*;
 
// Main class
class GFG {
 
    // Main driver method
    public static void main(String args[])
    {
 
        // Creating empty priority queue
        PriorityQueue<Integer> pQueue
            = new PriorityQueue<Integer>(
                Collections.reverseOrder());
 
        // Adding items to our priority queue
        // using add() method
        pQueue.add(10);
        pQueue.add(30);
        pQueue.add(20);
        pQueue.add(400);
 
        // Printing the most priority element
        System.out.println("Head value using peek function:"
                           + pQueue.peek());
 
        // Printing all elements
        System.out.println("The queue elements:");
        Iterator itr = pQueue.iterator();
        while (itr.hasNext())
            System.out.println(itr.next());
 
        // Removing the top priority element (or head) and
        // printing the modified pQueue using poll()
        pQueue.poll();
        System.out.println("After removing an element "
                           + "with poll function:");
        Iterator<Integer> itr2 = pQueue.iterator();
        while (itr2.hasNext())
            System.out.println(itr2.next());
 
        // Removing 30 using remove() method
        pQueue.remove(30);
        System.out.println("after removing 30 with"
                           + " remove function:");
 
        Iterator<Integer> itr3 = pQueue.iterator();
        while (itr3.hasNext())
            System.out.println(itr3.next());
 
        // Check if an element is present using contains()
        boolean b = pQueue.contains(20);
        System.out.println("Priority queue contains 20 "
                           + "or not?: " + b);
 
        // Getting objects from the queue using toArray()
        // in an array and print the array
        Object[] arr = pQueue.toArray();
        System.out.println("Value in array: ");
 
        for (int i = 0; i < arr.length; i++)
            System.out.println("Value: "
                               + arr[i].toString());
    }
}

Head value using peek function:400
The queue elements:
400
30
20
10
After removing an element with poll function:
30
10
20
after removing 30 with remove function:
20
10
Priority queue contains 20 or not?: true
Value in array: 
Value: 20
Value: 10