Cómo implementar la estructura de Heap Data en JavaScript

En este tutorial, aprenderemos sobre la estructura de datos del montón y su implementación en javascript.

Nota: si no está familiarizado con los árboles, consulte mi último tutorial

Índice
  1. ¿Qué es un montón?
  2. Implementación de montón
  3. Implementación de algoritmos
  4. Implementando el método hundirse
  5. Código y pruebas

¿Qué es un montón?

Un montón es una estructura de datos de árbol que satisface la propiedad del montón, si el nodo principal es mayor que el nodo secundario se denomina montón máximo o si el nodo principal es menor que el nodo secundario se denomina montón mínimo.

La implementación común del montón es el montón binario, que es un árbol binario. vea el árbol a continuación, que es un montón máximo binario donde el nodo principal es mayor que el nodo secundario.



JavaScript de almacenamiento dinámico máximo binario

Implementación de montón

El enfoque más común es almacenar el montón en una matriz porque el montón es siempre un árbol binario completo. No se requieren espacios para los punteros; en cambio, el padre y los hijos de cada nodo se pueden encontrar mediante cálculos simples.



ejemplo de implementación de montón binario

Sea 'i' el índice de la matriz el elemento de arr[i] Los niños se pueden encontrar en arr[2i+1] y arr[2i+2] y su índice padre arr[Math.floor((i-1)/2)]

Ejemplo: Busquemos los hijos del elemento 30 en la imagen de arriba.

  1. el índice del elemento 30 es 0
  2. hijo izquierdo = 2x0+1 -> 1
  3. hijo derecho = 2x0+2 -> 2
  4. Elemento 30 niños son arr[1] y arr[2] que es 20 y 10.

Implementación de algoritmos

Primero, necesitamos declarar una clase llamada Binary heap con la propiedad heap.

class  BinaryHeap{


  constructor(){
    this.heap = [30, 20, 10, 7, 9, 5]
  }

}

Método de inserción

El método Insert inserta un nuevo valor en el montón.

  1. Cree un nuevo método llamado insertar que acepte el valor como primer argumento.
  2. Empuje el valor hasta el último en el montón.
  3. a continuación, debemos invocar el método bubbleUp (también conocido como percolate-up, sift-up, trickle-up, swim-up, heapify-up o cascade-up).
  4. método de burbujeo
    • declarar una variable llamada índice e inicializar con el último índice en el montón.
  • siempre que el índice sea mayor que 0
  • declarar tres variables elemento,índicepadre,padre.
  • si el padre es mayor o igual que el elemento, rompe el ciclo.
  • intercambiar el padre y el elemento.
  insert(value){

    this.heap.push(value)
     this.bubbleUp()
  }

     bubbleUp(){
       let index =  this.heap.length-1;

    while( index > 0){
       let element = this.heap[index],
           parentIndex = Math.floor((index-1)/2),
           parent = this.heap[parentIndex],

       if(parent >= element) break
          this.heap[index] = parent;
         this.heap[parentIndex] = element;
          index = parentIndex

    }
  }

Déjame explicarte lo que sucede cuando ejecutas un método de burbuja.

  • primero almacenamos un índice del elemento insertado.
  • si el índice es mayor que 0 significa que nuestro índice está presente en el montón.
  • como comienza el ciclo
  • si el padre es mayor o igual que el elemento, salimos del bucle.
  • si padre es menor que hijo, intercambia padre e hijo.

Esto nos ayuda a eliminar el elemento superior del montón.

El procedimiento de eliminar la raíz del montón y restaurar las propiedades se llama descenso (también conocido como burbujear, filtrar, tamizar, bajar del montón, goteo, catasificación, cascada y extracción mín./máx.) .

El elemento más alto en el montón presente en el índice 0, por lo que debemos eliminar el primer elemento y reemplazarlo con el último elemento y ejecutar el método de descenso.

¿Cómo funciona el método ExtractMax usando diagramas?



método de fregadero parte 1

2.


fregadero parte 2

3.


fregadero parte 3

4.


fusión parte 4

Implementemos un algoritmo ExtractMax

pseudocódigo

  1. crea un método llamado extract max.
  2. declare una variable llamada max e inicialice con el primer elemento del montón.
  3. actualice el primer elemento del montón con el último elemento.
  4. Ejecute el método de sumidero.
  5. retorno máximo
extractMax(){
    let  max = this.heap[0];
    this.heap[0]= this.heap.pop()
    this.sinkDown(0)
   return max
  }

Implementando el método hundirse

  • Consulte los diagramas anteriores, obtendrá claridad sobre cómo funciona el método hundirse.
 sinkDown(index){
     let   left = 2*index+1,
           right = 2*index+2,
           largest = index;
     const length = this.heap.length


        
      if(left <= length &&  this.heap[left]>this.heap[largest] ){
         largest = left
       }
      
      if(right <= length && this.heap[right]>this.heap[largest]) {
        largest = right
      }
     
     if(largest !== index){
        [this.heap[largest],this.heap[index]] =
        [this.heap[index],this.heap[largest]]
       this.sinkDown(largest)
     }

  }

Código y pruebas

Si quieres conocer otros artículos parecidos a Cómo implementar la estructura de Heap Data en JavaScript puedes visitar la categoría Tutoriales.

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Subir

Esta página web utiliza cookies para analizar de forma anónima y estadística el uso que haces de la web, mejorar los contenidos y tu experiencia de navegación. Para más información accede a la Política de Cookies . Ver mas