¿Cómo funciona la estructura de datos "binary heap"? - Educa Sistemas

Breaking

Post Top Ad

Post Top Ad

sábado, 10 de agosto de 2019

¿Cómo funciona la estructura de datos "binary heap"?

¡Esta es una hermosa estructura de datos basada en tree!
Su estructura permite almacenar cada dato en un arreglo, a diferencia de un binary tree común que debe tener un puntero al siguiente nodo de manera explicita, binary heap es por tanto una estructura implícita . Esto es posible porque es un complete binary tree.
Existe dos manera de construir un binary heap, basada en el menor o mayor elemento. En este ejemplo usare el menor.
Supongamos que tenemos un binary heap con los siguientes datos:
5,10,15,20
Se vería así:
Ahora necesitamos insertar dos valores: 11 y 1.
Como vemos el 11 queda como hijo del nodo 10, porque 11 es mayor a 10. Ahora en el caso del valor 1 es distinto, es aquí donde podemos ver la característica del binary heap, como estamos trabajando con el menor, el 1 no puede quedar como hoja (es decir al final). Entonces, comparamos con su padre(15) si es menor, entonces hace swap (intercambio), sucesivamente hasta que 1 sea mayor o este en el nodo raíz. Como vemos ahora el 1 queda como nodo raíz porque es menor a 15 y 5. Esto quiere decir que podemos acceder al menor elemento del tree en O(1)!!
Otro dato interesante es el tiempo de computo para la operación anterior de insertar un elemento, es de O(logn) en promedio y en el mejor de los caso es O(1)(por ejemplo cuando agregamos el nodo 11). Este árbol tiene una altura de 3 porque el total de nodos es de 6,6/2=3.
Otra operación interesante de binary heap es la eliminación del menor valor, es decir el nodo raíz.
Primero se intercambia el último nodo(15) con la raíz(1), se elimina el nodo 1, ahora comprobamos si 15 es mayor a 5, si es así, hace swap. Quedando el valor 5 como menor y en la raíz lo cual es correcto. Esta operación tiene la misma complejidad algorítmica de la operación de insertar.
La operación insert y deleteMin son operaciones dinámicas porque modifican la estructura. Una operación como find o peek (retorna la raíz sin eliminarla) serían estáticas porque no modifican la estructura.
Ahora como habíamos dicho, lo interesante de binary heap es que todos los datos están almacenados en un array de una dimensión, donde podemos movernos entre nodos con unas simples operaciones.
Por ejemplo para saber cual es el padre del nodo 15, sería: floor(6/2)=3, es decir el nodo 5.
Por otro lado para saber los nodos hijo de la raíz sería, izquierda: 21=2=>nodo10 y derecha: 21+1=3=>nodo5.

Es simple de implementar; aquí un ejemplo en Julia que programe hace un rato con las operaciones que mencione (usando los mismo datos):
  1. mutable struct Heap
  2. data :: Vector{Int}
  3. size :: Int
  4. Heap() = new(zeros(Int, 2), 0)
  5. end
  6.  
  7. function printHeap(h :: Heap)
  8. println(h.data[1:h.size])
  9. end
  10.  
  11. function resize(h :: Heap)
  12. resize!(h.data, length(h.data) * 2)
  13. end
  14.  
  15. function deleteMin(h :: Heap)
  16. if h.size == 0
  17. return []
  18. end
  19. h.data[1], h.data[h.size] = h.data[h.size], h.data[1] # swap
  20. h.data[h.size] = -1
  21. h.size -= 1
  22.  
  23. value = h.data[1]
  24. pos = 1
  25. while pos < h.size - 1
  26. pivot = pos * 2
  27. if h.data[pivot] <= value
  28. h.data[pos], h.data[pivot] = h.data[pivot], h.data[pos] # swap
  29. pos = pivot
  30. else
  31. break
  32. end
  33. end
  34. end
  35.  
  36. function insert(h :: Heap, value :: Int)
  37. if h.size == length(h.data) - 1
  38. resize(h)
  39. end
  40. h.size += 1
  41. pos = h.size
  42.  
  43. h.data[pos] = value
  44. while pos > 1
  45. pivot = Int(floor(pos / 2))
  46. if h.data[pivot] >= value
  47. h.data[pos], h.data[pivot] = h.data[pivot], h.data[pos] # swap
  48. pos = pivot
  49. else
  50. break
  51. end
  52. end
  53. end
  54.  
  55. heap = Heap()
  56. insert(heap, 5)
  57. printHeap(heap)
  58.  
  59. insert(heap, 10)
  60. printHeap(heap)
  61.  
  62. insert(heap, 15)
  63. printHeap(heap)
  64.  
  65. insert(heap, 20)
  66. printHeap(heap)
  67.  
  68. insert(heap, 11)
  69. printHeap(heap)
  70.  
  71. insert(heap, 1)
  72. printHeap(heap)
  73.  
  74. deleteMin(heap)
  75. printHeap(heap)
  76.  
  77. deleteMin(heap)
  78. printHeap(heap)
  79.  
  80. deleteMin(heap)
  81. printHeap(heap)
  82.  
  83. deleteMin(heap)
  84. printHeap(heap)
  85.  
  86. deleteMin(heap)
  87. printHeap(heap)
Nótese que hago una amortización con la función resize (se va agrandando el tamaño del array por 2), para que la inserción pueda ser en O(1)en el mejor de los casos, y no tenga que reconstruir le array.
Resultado:
  1. [5]
  2. [5, 10]
  3. [5, 10, 15]
  4. [5, 10, 15, 20]
  5. [5, 10, 15, 20, 11]
  6. [1, 10, 5, 20, 11, 15]
  7. [10, 15, 5, 20, 11]
  8. [11, 15, 5, 20]
  9. [15, 20, 5]
  10. [5, 20]
  11. [20]
¿Divertido no crees? :-)

PD: Esta estructura es útil para usarla dentro de otra estructura llamada: priority queue, esta va ordenando los nodos según su prioridad. La cual se utiliza en infinidad de sistemas porque existen procesos que pueden llegar tarde pero que requieren mayor prioridad para ejecutarse que otros que llegaron antes.

Post Top Ad

Responsive Ads Here