Estructura de datos del montón

En este tutorial, aprenderá qué es la estructura de datos del montón. Además, encontrará ejemplos prácticos de operaciones de montón en C, C ++, Java y Python.

La estructura de datos del montón es un árbol binario completo que satisface la propiedad del montón . También se denomina montón binario .

Un árbol binario completo es un árbol binario especial en el que

  • todos los niveles, excepto posiblemente el último, se llenan
  • todos los nodos están lo más a la izquierda posible

Heap Property es la propiedad de un nodo en el que

  • (para max heap) la clave de cada nodo es siempre mayor que sus nodos secundarios y la clave del nodo raíz es la más grande entre todos los demás nodos;
  • (para min heap) la clave de cada nodo es siempre más pequeña que los nodos secundarios y la clave del nodo raíz es la más pequeña entre todos los demás nodos.

Operaciones de montón

Algunas de las operaciones importantes realizadas en un montón se describen a continuación junto con sus algoritmos.

Amontonar

Heapify es el proceso de crear una estructura de datos de pila a partir de un árbol binario. Se utiliza para crear un Min-Heap o un Max-Heap.

  1. Deje que la matriz de entrada sea
  2. Cree un árbol binario completo a partir de la matriz
  3. Comience desde el primer índice del nodo no hoja cuyo índice está dado por n/2 - 1.
  4. Establecer el elemento actual icomo largest.
  5. El índice de hijo izquierdo es dado por 2i + 1y el hijo derecho es dado por 2i + 2.
    Si leftChildes mayor que currentElement(es decir, elemento en el ithíndice), se establece leftChildIndexcomo mayor.
    Si rightChildes mayor que el elemento en largest, se establece rightChildIndexcomo largest.
  6. Intercambiar largestconcurrentElement
  7. Repita los pasos 3 a 7 hasta que los subárboles también estén agrupados.

Algoritmo

 Heapify(array, size, i) set i as largest leftChild = 2i + 1 rightChild = 2i + 2 if leftChild > array(largest) set leftChildIndex as largest if rightChild > array(largest) set rightChildIndex as largest swap array(i) and array(largest)

Para crear un Max-Heap:

 MaxHeap(array, size) loop from the first index of non-leaf node down to zero call heapify

Para Min-Heap, ambos leftChildy rightChilddeben ser más pequeños que el padre para todos los nodos.

Insertar elemento en montón

Algoritmo para la inserción en Max Heap

 If there is no node, create a newNode. else (a node is already present) insert the newNode at the end (last node from left to right.) heapify the array
  1. Inserte el nuevo elemento al final del árbol.
  2. Apila el árbol.

Para Min Heap, el algoritmo anterior se modifica para que parentNodesiempre sea menor que newNode.

Eliminar elemento del montón

Algoritmo para la eliminación en Max Heap

 If nodeToBeDeleted is the leafNode remove the node Else swap nodeToBeDeleted with the lastLeafNode remove noteToBeDeleted heapify the array
  1. Seleccione el elemento a eliminar.
  2. Cámbielo por el último elemento.
  3. Quite el último elemento.
  4. Apila el árbol.

Para Min Heap, el algoritmo anterior se modifica para que ambos childNodessean mayores menores que currentNode.

Peek (encontrar máximo / mínimo)

La operación Peek devuelve el elemento máximo de Max Heap o el elemento mínimo de Min Heap sin eliminar el nodo.

Para Max heap y Min Heap

 devolver rootNode

Extraer-Max / Min

Extract-Max devuelve el nodo con el valor máximo después de eliminarlo de un montón máximo, mientras que Extract-Min devuelve el nodo con el mínimo después de eliminarlo del montón mínimo.

Ejemplos de Python, Java, C / C ++

Python Java C C ++ 
 # Max-Heap data structure in Python def heapify(arr, n, i): largest = i l = 2 * i + 1 r = 2 * i + 2 if l < n and arr(i) < arr(l): largest = l if r < n and arr(largest) < arr(r): largest = r if largest != i: arr(i),arr(largest) = arr(largest),arr(i) heapify(arr, n, largest) def insert(array, newNum): size = len(array) if size == 0: array.append(newNum) else: array.append(newNum); for i in range((size//2)-1, -1, -1): heapify(array, size, i) def deleteNode(array, num): size = len(array) i = 0 for i in range(0, size): if num == array(i): break array(i), array(size-1) = array(size-1), array(i) array.remove(num) for i in range((len(array)//2)-1, -1, -1): heapify(array, len(array), i) arr = () insert(arr, 3) insert(arr, 4) insert(arr, 9) insert(arr, 5) insert(arr, 2) print ("Max-Heap array: " + str(arr)) deleteNode(arr, 4) print("After deleting an element: " + str(arr)) 
  // Max-Heap data structure in Java import java.util.ArrayList; class Heap ( void heapify(ArrayList hT, int i) ( int size = hT.size(); int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l hT.get(largest)) largest = l; if (r hT.get(largest)) largest = r; if (largest != i) ( int temp = hT.get(largest); hT.set(largest, hT.get(i)); hT.set(i, temp); heapify(hT, largest); ) ) void insert(ArrayList hT, int newNum) ( int size = hT.size(); if (size == 0) ( hT.add(newNum); ) else ( hT.add(newNum); for (int i = size / 2 - 1; i>= 0; i--) ( heapify(hT, i); ) ) ) void deleteNode(ArrayList hT, int num) ( int size = hT.size(); int i; for (i = 0; i = 0; j--) ( heapify(hT, j); ) ) void printArray(ArrayList array, int size) ( for (Integer i : array) ( System.out.print(i + " "); ) System.out.println(); ) public static void main(String args()) ( ArrayList array = new ArrayList(); int size = array.size(); Heap h = new Heap(); h.insert(array, 3); h.insert(array, 4); h.insert(array, 9); h.insert(array, 5); h.insert(array, 2); System.out.println("Max-Heap array: "); h.printArray(array, size); h.deleteNode(array, 4); System.out.println("After deleting an element: "); h.printArray(array, size); ) )
 // Max-Heap data structure in C #include int size = 0; void swap(int *a, int *b) ( int temp = *b; *b = *a; *a = temp; ) void heapify(int array(), int size, int i) ( if (size == 1) ( printf("Single element in the heap"); ) else ( int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l array(largest)) largest = l; if (r array(largest)) largest = r; if (largest != i) ( swap(&array(i), &array(largest)); heapify(array, size, largest); ) ) ) void insert(int array(), int newNum) ( if (size == 0) ( array(0) = newNum; size += 1; ) else ( array(size) = newNum; size += 1; for (int i = size / 2 - 1; i>= 0; i--) ( heapify(array, size, i); ) ) ) void deleteRoot(int array(), int num) ( int i; for (i = 0; i  = 0; i--) ( heapify(array, size, i); ) ) void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) printf("%d ", array(i)); printf(""); ) int main() ( int array(10); insert(array, 3); insert(array, 4); insert(array, 9); insert(array, 5); insert(array, 2); printf("Max-Heap array: "); printArray(array, size); deleteRoot(array, 4); printf("After deleting an element: "); printArray(array, size); ) 
 // Max-Heap data structure in C++ #include #include using namespace std; void swap(int *a, int *b) ( int temp = *b; *b = *a; *a = temp; ) void heapify(vector &hT, int i) ( int size = hT.size(); int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l hT(largest)) largest = l; if (r hT(largest)) largest = r; if (largest != i) ( swap(&hT(i), &hT(largest)); heapify(hT, largest); ) ) void insert(vector &hT, int newNum) ( int size = hT.size(); if (size == 0) ( hT.push_back(newNum); ) else ( hT.push_back(newNum); for (int i = size / 2 - 1; i>= 0; i--) ( heapify(hT, i); ) ) ) void deleteNode(vector &hT, int num) ( int size = hT.size(); int i; for (i = 0; i  = 0; i--) ( heapify(hT, i); ) ) void printArray(vector &hT) ( for (int i = 0; i < hT.size(); ++i) cout << hT(i) << " "; cout << ""; ) int main() ( vector heapTree; insert(heapTree, 3); insert(heapTree, 4); insert(heapTree, 9); insert(heapTree, 5); insert(heapTree, 2); cout << "Max-Heap array: "; printArray(heapTree); deleteNode(heapTree, 4); cout << "After deleting an element: "; printArray(heapTree); )

Aplicaciones de estructura de datos de montón

  • El montón se utiliza al implementar una cola de prioridad.
  • Algoritmo de Dijkstra
  • Ordenar montón

Articulos interesantes...