A montón máximo es un árbol binario completo en el que el valor en cada nodo interno es mayor o igual a los valores en los hijos de ese nodo. Mapear los elementos de un montón en una matriz es trivial: si un nodo 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 normalmente se representa como una matriz. El elemento raíz estará en Arr[0]. La siguiente tabla muestra índices de otros nodos para el con nodo, es decir, Arr[i]:
Arr[(i-1)/2] Devuelve el nodo padre.
Arr[(2*i)+1] Devuelve el nodo secundario izquierdo.
Arr[(2*i)+2] Devuelve el nodo secundario derecho.
Las operaciones en Max Heap son las siguientes:
- obtenerMax(): Devuelve el elemento raíz de Max Heap. La complejidad temporal de esta operación es O(1) .
- extraerMax(): Elimina el elemento máximo de montón máximo . La complejidad temporal de esta operación es O(Iniciar sesión n) ya que esta operación necesita mantener la propiedad del montón llamando al método montón () después de quitar la raíz.
- insertar(): Insertar una nueva clave requiere O(Iniciar sesión n) tiempo. Agregamos una nueva clave al final del árbol. Si la nueva clave es más pequeña que su clave principal, entonces no necesitamos hacer nada. De lo contrario, debemos recorrer hacia arriba para corregir la propiedad del montón violada.
Nota: En la siguiente implementación, indexamos desde el índice 1 para simplificar la implementación.
Métodos:
Hay 2 métodos mediante los cuales podemos lograr el objetivo que se enumeran:
- Enfoque básico creando maxHeapify() método
- Usando Colecciones.reverseOrder() método a través de funciones de biblioteca
Método 1: Enfoque básico creando maxHeapify() método
Crearemos un método asumiendo que los subárboles izquierdo y derecho ya están agrupados, solo necesitamos arreglar la raíz.
Ejemplo
Java
// 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 if given node is leaf> >private> boolean> isLeaf(>int> pos)> >{> >if> (pos>(tamaño />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[pos] if (Heap[leftChild(pos)]>Montón[rightChild(pos)]) { swap(pos, leftChild(pos)); maxHeapify(leftChild(pos)); } else { swap(pos, rightChild(pos)); maxHeapify(rightChild(pos)); } } } // Método 7 // Inserta un nuevo elemento en el montón máximo public void insert(int element) { Heap[size] = element; // Recorrer hacia arriba y corregir la propiedad violada int current = size; while (Montón[actual]> Montón[padre(actual)]) { swap(actual, padre(actual)); actual = padre (actual); } tamaño++; } // Método 8 // Para mostrar el montón public void print() { for (int i = 0; i 2; i++) { System.out.print('Parent Node : ' + Heap[i]); if (leftChild(i) // si el niño está fuera del límite // de la matriz System.out.print(' Left Child Node: ' + Heap[leftChild(i)]); if (rightChild(i) ) // el índice secundario correcto // no debe estar fuera del índice de la matriz System.out.print(' Right Child Node: ' + Heap[rightChild(i)]); ; // para nueva línea } } // Método 9 // Eliminar un elemento del montón máximo public int extractMax() { int popped = Heap[0] = Heap[--size]; ; return popped; } // Método 10 // método del controlador principal public static void main(String[] arg) { // Mostrar mensaje para una mejor legibilidad System.out.println('The Max Heap is '); = new MaxHeap(15); // Insertar nodos // Entradas personalizadas maxHeap.insert(5); maxHeap.insert(84); maxHeap.insert(19); maxHeap.insert(6); maxHeap.insert(22); maxHeap.insert(9); // Llamando a maxHeap() como se define arriba maxHeap.print(); valor en el montón System.out.println('El valor máximo es ' + maxHeap.extractMax()); } }> |
>
propiedades ácidas en dbms
>Producción
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: Usando el método Collections.reverseOrder() a través de funciones de biblioteca
Usamos la clase PriorityQueue para implementar Heaps en Java. De forma predeterminada, esta clase implementa Min Heap. Para implementar Max Heap, utilizamos el método Collections.reverseOrder().
Ejemplo
Java
// 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 pQueue> >=>new> PriorityQueue(> >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 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 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 System.out.println('Value: ' + arr[i].toString()); } }> |
>
>Producción
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>