Un Min-Heap es un árbol binario completo en el que el valor de cada Node interno es menor o igual que los valores de los elementos secundarios de ese Node. Mapear los elementos de un montón en 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:
5 13
/ \ / \
10 15 16 31
/ / \ / \
30 41 51 100 41
Repasemos la representación de Min heap. Básicamente, Min Heap es un árbol binario completo. Un montón mínimo normalmente se representa como una array. El elemento raíz estará en Arr[0] . Para cualquier i-ésimo Node, es decir, Arr[i]
- Arr[(i -1) / 2] devuelve su Node principal.
- Arr[(2 * i) + 1] devuelve su Node secundario izquierdo.
- Arr[(2 * i) + 2] devuelve su Node secundario derecho.
Ahora analicemos las operaciones en Min Heap, que son las siguientes:
- getMin(): Devuelve el elemento raíz de Min Heap. La complejidad temporal de esta operación es O(1) .
- extractMin(): elimina el elemento mínimo de MinHeap. 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 a 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 una nueva clave es más grande que su padre, entonces no necesitamos hacer nada. De lo contrario, debemos recorrer hacia arriba para corregir la propiedad del montón violada.
Ejemplo 1:
Java
// Java Program to Implement Heaps
// by Illustrating Min Heap
// Main class (MinHeap)
class GFG {
// Member variables of this class
private int[] Heap;
private int size;
private int maxsize;
// Initializing front as static with unity
private static final int FRONT = 1;
// Constructor of this class
public GFG(int maxsize)
{
// This keyword refers to current object itself
this.maxsize = maxsize;
this.size = 0;
Heap = new int[this.maxsize + 1];
Heap[0] = Integer.MIN_VALUE;
}
// Method 1
// Returning the position of
// the parent for the node currently
// at pos
private int parent(int pos) { return pos / 2; }
// Method 2
// Returning the position of the
// left child for the node currently at pos
private int leftChild(int pos) { return (2 * pos); }
// Method 3
// Returning the position of
// the right child for the node currently
// at pos
private int rightChild(int pos)
{
return (2 * pos) + 1;
}
// Method 4
// Returning true if the passed
// node is a leaf node
private boolean isLeaf(int pos)
{
if (pos > (size / 2)) {
return true;
}
return false;
}
// Method 5
// To swap two nodes of the heap
private void swap(int fpos, int spos)
{
int tmp;
tmp = Heap[fpos];
Heap[fpos] = Heap[spos];
Heap[spos] = tmp;
}
// Method 6
// To heapify the node at pos
private void minHeapify(int pos)
{
if(!isLeaf(pos)){
//swap with the minimum of the two children
int swapPos = Heap[leftChild(pos)]<Heap[rightChild(pos)]?leftChild(pos):rightChild(pos);
if(Heap[pos]>Heap[leftChild(pos)] || Heap[pos]> Heap[rightChild(pos)]){
swap(pos,swapPos);
minHeapify(swapPos);
}
}
}
// Method 7
// To insert a node into the heap
public void insert(int element)
{
if (size >= maxsize) {
return;
}
Heap[++size] = element;
int current = size;
while (Heap[current] < Heap[parent(current)]) {
swap(current, parent(current));
current = parent(current);
}
}
// Method 8
// To print the contents of the heap
public void print()
{
for (int i = 1; i <= size / 2; i++) {
// Printing the parent and both childrens
System.out.print(
" PARENT : " + Heap[i]
+ " LEFT CHILD : " + Heap[2 * i]
+ " RIGHT CHILD :" + Heap[2 * i + 1]);
// By here new line is required
System.out.println();
}
}
// Method 9
// To remove and return the minimum
// element from the heap
public int remove()
{
int popped = Heap[FRONT];
Heap[FRONT] = Heap[size--];
minHeapify(FRONT);
return popped;
}
// Method 10
// Main driver method
public static void main(String[] arg)
{
// Display message
System.out.println("The Min Heap is ");
// Creating object opf class in main() methodn
GFG minHeap = new GFG(15);
// Inserting element to minHeap
// using insert() method
// Custom input entries
minHeap.insert(5);
minHeap.insert(3);
minHeap.insert(17);
minHeap.insert(10);
minHeap.insert(84);
minHeap.insert(19);
minHeap.insert(6);
minHeap.insert(22);
minHeap.insert(9);
// Print all elements of the heap
minHeap.print();
// Removing minimum value from above heap
// and printing it
System.out.println("The Min val is "
+ minHeap.remove());
}
}
Producción
The Min Heap is PARENT : 3 LEFT CHILD : 5 RIGHT CHILD :6 PARENT : 5 LEFT CHILD : 9 RIGHT CHILD :84 PARENT : 6 LEFT CHILD : 19 RIGHT CHILD :17 PARENT : 9 LEFT CHILD : 22 RIGHT CHILD :10 The Min val is 3
Usamos la clase PriorityQueue para implementar Heaps en Java. De forma predeterminada, esta clase implementa Min Heap, que se muestra en el siguiente ejemplo:
Ejemplo 2:
Java
// Java program to Demonstrate working of PriorityQueue
// Using Library Functions
// Importing 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>();
// Adding items to the 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:");
// Iterating over objects using Iterator
// so do creating an Iterator class
Iterator itr = pQueue.iterator();
// Iterating toill there is single element left in
// object using next() method
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:");
// Again creating iterator object
Iterator<Integer> itr2 = pQueue.iterator();
while (itr2.hasNext())
System.out.println(itr2.next());
// Removing 30 using remove()
pQueue.remove(30);
System.out.println("after removing 30 with"
+ " remove function:");
// Again creating iterator object
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());
}
}
Producción:
Head value using peek function:10 The queue elements: 10 30 20 400 After removing an element with poll function: 20 30 400 after removing 30 with remove function: 20 400 Priority queue contains 20 or not?: true Value in array: Value: 20 Value: 400
Publicación traducida automáticamente
Artículo escrito por Amaninder.Singh y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA