Heap

Las heaps son estructuras de datos avanzadas útiles en aplicaciones donde se desea ordenar e implementar colas de prioridad. Son árboles binarios regulares con dos propiedades especiales.

Prioridad de orden de una Heap

La propiedad de orden de heap es diferente para las siguientes dos estructuras:

• Min Heap
• Max Heap

Los Min Heaps se construyen en base a la propiedad Min Heap y los Max Heaps se construyen en base a la propiedad Max Heap. Veamos cómo son diferentes.

Propiedad de Max Heap

Todas las claves del nodo padre deben ser mayores o iguales a sus claves de nodo hijas en una max heap. Por lo tanto, el nodo raíz siempre contendrá el elemento más grande en la heap. Si el nodo A tiene un nodo secundario B, entonces:

key(A)≥key(B)

Propiedad de Min Heap

En Min Heaps, todas las claves del nodo padre son menores o iguales a sus claves del nodo hijo. Por lo tanto, el nodo raíz, en este caso, siempre contendrá el elemento más pequeño presente en la heap. Si el nodo A tiene un nodo secundario B, entonces:

key(A)≤key(B)

Implementación

Código de ejemplo

package main

import (
  "container/heap"
  "fmt"
)

func main() {
  minHeap := &Heap{3, 1, 4, 5, 1, 2, 6}
  heap.Init(minHeap)
  heap.Push(minHeap, -10)

  fmt.Println("Elementos:", minHeap)
  fmt.Println("Longitud:", minHeap.Len())

  fmt.Println("Elemento mínimo:", heap.Pop(minHeap))
  fmt.Println("Elemento mínimo:", heap.Pop(minHeap))
  fmt.Println("Elemento mínimo:", heap.Pop(minHeap))
  fmt.Println("Elemento mínimo:", heap.Pop(minHeap))

  fmt.Println("Longitud:", minHeap.Len())
  fmt.Println("Elementos:", minHeap)
}

// Heap contiene los elementos de la heap.
type Heap []int

// Less compara los elementos y determina si es una `min heap` o `max heap`
// si usamos `<` se trata de una min heap, si queremos usar una max heap
// cambiamos a `>`.
func (h Heap) Less(i, j int) bool {
  return h[i] < h[j]
}

// Len determina la longitud de la (min/max) heap.
func (h Heap) Len() int {
  return len(h)
}

// Swap hace el intercambio de los elementos dentro de la (min/max) heap.
func (h Heap) Swap(i, j int) {
  h[i], h[j] = h[j], h[i]
}

// Push añade un nuevo elemento a la (min/max) heap.
func (h *Heap) Push(val any) {
  *h = append(*h, val.(int))
}

// Pop remueve el elemento menor/mayor dependiendo de la heap.
func (h *Heap) Pop() any {
  old := *h
  n := len(old)
  x := old[n-1]
  *h = old[0 : n-1]
  return x
}

Ejecuta el código en este playground.