0Pricing
Coding Interview Prep · Lección

Propiedad del heap y representación en array

Comprenda la estructura de árbol binario completo almacenada como array, derive las fórmulas de índices de padres e hijos y visualice las operaciones sift-up y sift-down.

Propiedad del heap y representación en array es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 1 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.

¿Qué es un heap?

Un heap es un árbol binario completo especializado que cumple la propiedad de heap: en un min-heap, cada padre es menor o igual que sus hijos; en un max-heap, cada padre es mayor o igual que sus hijos. Esta propiedad garantiza que el elemento mínimo (o máximo) siempre esté en la raíz, lo que permite acceder al elemento extremo en O(1). Los heaps son la estructura de datos en la que se basan las colas de prioridad.

# Min-heap example:
#         1
#        / \
#       3   2
#      / \ / \
#     7  4 5  6
# Every parent <= its children
# Root (1) is always the minimum

# Max-heap example:
#         9
#        / \
#       7   8
#      / \ / \
#     3  4 5  6
# Every parent >= its children
# Root (9) is always the maximum
print('Heap property: parent dominates all descendants')

Estructura de árbol binario completo

Un heap se almacena como un árbol binario completo: todos los niveles están completamente llenos, excepto posiblemente el último, que se llena de izquierda a derecha. Esta estructura permite una elegante representación mediante un array, sin espacio desperdiciado ni punteros. La propiedad de completitud garantiza que la altura del heap siempre sea floor(log₂ n), lo que asegura operaciones de push y pop en O(log n).

# Complete binary tree properties:
# 1. All levels filled except possibly the last
# 2. Last level filled from LEFT to right
# 3. For n nodes: height = floor(log2(n))

# NOT complete (last level not left-filled):
#     1
#    / \
#   2   3
#        \
#         4  <- right child without left sibling

# Valid complete binary tree with 4 nodes:
#     1
#    / \
#   2   3
#  /
# 4
print('Complete BT: height = floor(log2(n)) always')

Representación de un heap mediante un array

La estructura de árbol binario completo permite almacenar un heap en un array sin ningún puntero. Para un nodo en el índice i (indexado desde 0), su padre está en (i-1) // 2, su hijo izquierdo en 2i+1 y su hijo derecho en 2i+2. Esta aritmética entera reemplaza el recorrido mediante punteros y hace que los heaps sean extremadamente eficientes para la caché.

# Array representation (0-indexed):
# Index:  0  1  2  3  4  5  6
# Array: [1, 3, 2, 7, 4, 5, 6]
# Tree:        1          (index 0)
#             / \         
#            3   2        (indices 1, 2)
#           / \ / \       
#          7  4 5  6      (indices 3,4,5,6)

# Index formulas (0-based):
def parent(i):      return (i - 1) // 2
def left_child(i):  return 2 * i + 1
def right_child(i): return 2 * i + 2

heap = [1, 3, 2, 7, 4, 5, 6]
print('Parent of index 3:', parent(3), '-> value', heap[parent(3)])
print('Left child of 1:', left_child(1), '-> value', heap[left_child(1)])

Sift-up: restaurar el heap después de insertar

Sift-up (también llamado bubble-up o heapify-up) se utiliza después de insertar un elemento nuevo al final del array del heap. Compare el elemento nuevo con su padre; si se infringe la propiedad de heap, intercámbielos y continúe hacia arriba. Repita el proceso hasta que el elemento esté en la posición correcta o llegue a la raíz. Esta operación se ejecuta en O(log n) porque la altura del árbol es O(log n).

def sift_up(heap, i):
    while i > 0:
        p = (i - 1) // 2  # parent index
        if heap[p] > heap[i]:  # min-heap: parent should be smaller
            heap[p], heap[i] = heap[i], heap[p]
            i = p
        else:
            break  # heap property restored

# Demonstrate: insert 0 into an existing min-heap
heap = [1, 3, 2, 7, 4, 5, 6]
heap.append(0)  # add at end
print('Before sift-up:', heap)
sift_up(heap, len(heap) - 1)
print('After sift-up:', heap)  # 0 should bubble to root

Sift-down: restaurar el heap después de extraer

Sift-down (heapify-down) se utiliza después de eliminar la raíz. Mueva el último elemento a la raíz y, a continuación, desplácelo hacia abajo intercambiándolo repetidamente con el hijo menor (en un min-heap) hasta restaurar la propiedad de heap. Esta operación también se ejecuta en O(log n). Tanto sift-up como sift-down son los componentes básicos de todas las operaciones de heap.

def sift_down(heap, i, n):
    while True:
        smallest = i
        l = 2 * i + 1  # left child
        r = 2 * i + 2  # right child
        if l < n and heap[l] < heap[smallest]:
            smallest = l
        if r < n and heap[r] < heap[smallest]:
            smallest = r
        if smallest == i:
            break  # already in correct position
        heap[i], heap[smallest] = heap[smallest], heap[i]
        i = smallest

heap = [1, 3, 2, 7, 4, 5, 6]
# Pop min: move last to root, then sift-down
heap[0] = heap[-1]
heap.pop()
print('After move last to root:', heap)
sift_down(heap, 0, len(heap))
print('After sift-down:', heap)  # valid min-heap again

Construir un heap a partir de un array: algoritmo de Floyd

Insertar ingenuamente n elementos uno a uno requiere O(n log n). El algoritmo de heapify de Floyd construye un heap en O(n) aplicando sift-down a cada nodo que no sea hoja, empezando por el último nodo que no es hoja (índice n//2 - 1) y retrocediendo hasta la raíz. Los nodos hoja ya son heaps triviales, por lo que solo es necesario corregir los nodos internos; por eso el trabajo total suma O(n) en lugar de O(n log n).

def build_heap(arr):
    n = len(arr)
    # Start from last non-leaf node: index n//2 - 1
    for i in range(n // 2 - 1, -1, -1):
        sift_down(arr, i, n)
    return arr

arr = [5, 3, 8, 1, 9, 2, 7]
print('Before:', arr)
build_heap(arr)
print('After (min-heap):', arr)  # root should be 1

# Why O(n)? Most nodes are near the bottom (leaves).
# Level k from bottom has ~n/2^k nodes, each needing
# at most k swaps. Sum = n * sum(k/2^k) = O(n).

Heap sort usando el heap basado en un array

Heap sort se ejecuta en O(n log n) con O(1) de espacio adicional. Fase 1: construya un max-heap a partir del array en O(n). Fase 2: extraiga repetidamente el máximo intercambiando la raíz con el último elemento aún no ordenado y aplicando después sift-down al heap reducido. Tras n extracciones, el array queda ordenado de forma ascendente. Este algoritmo in-place demuestra cómo la representación mediante un array permite ordenar sin asignar una estructura de datos independiente.

def sift_down_max(arr, i, n):
    while True:
        largest = i
        l, r = 2*i+1, 2*i+2
        if l < n and arr[l] > arr[largest]: largest = l
        if r < n and arr[r] > arr[largest]: largest = r
        if largest == i: break
        arr[i], arr[largest] = arr[largest], arr[i]
        i = largest

def heap_sort(arr):
    n = len(arr)
    # Build max-heap
    for i in range(n // 2 - 1, -1, -1):
        sift_down_max(arr, i, n)
    # Extract elements one by one
    for end in range(n - 1, 0, -1):
        arr[0], arr[end] = arr[end], arr[0]  # move max to end
        sift_down_max(arr, 0, end)

arr = [5, 3, 8, 1, 9, 2, 7]
heap_sort(arr)
print(arr)  # [1, 2, 3, 5, 7, 8, 9]

Min-heap frente a max-heap

Un min-heap tiene el elemento menor en la raíz; al hacer pop siempre se obtiene el mínimo. Un max-heap tiene el elemento mayor en la raíz; al hacer pop siempre se obtiene el máximo. Ambos tienen la misma estructura y las mismas operaciones; solo cambia la dirección de la comparación. El módulo heapq de Python implementa únicamente un min-heap, por lo que debe negar los valores para simular un max-heap.

import heapq

# Python heapq is a MIN-HEAP
min_heap = []
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 3)
print('Min-heap min:', heapq.heappop(min_heap))  # 1

# Simulate MAX-HEAP by negating values
max_heap = []
for val in [5, 1, 3]:
    heapq.heappush(max_heap, -val)  # negate on push
print('Max-heap max:', -heapq.heappop(max_heap))  # 5 (negate on pop)

# For tuples: heapq sorts by first element
print(min_heap, max_heap)

Resumen de la complejidad de las operaciones de heap

Todas las operaciones de heap se basan en sift-up y sift-down, ambas con complejidad O(log n). Push: append + sift-up = O(log n). Pop: intercambiar la raíz con el último elemento + sift-down = O(log n). Peek: acceder al índice 0 = O(1). Construir el heap: O(n) mediante el algoritmo de Floyd. Heap sort: O(n log n). Estas complejidades hacen que los heaps sean la estructura ideal cuando necesita repetidamente el mínimo o el máximo de una colección dinámica.

# Heap complexity summary:
# Operation     | Time       | Space
# --------------|------------|-------
# Push          | O(log n)   | O(1)
# Pop (min/max) | O(log n)   | O(1)
# Peek          | O(1)       | O(1)
# Build from n  | O(n)       | O(1) in-place
# Heap sort     | O(n log n) | O(1)
# nlargest(k,n) | O(n log k) | O(k)

import heapq
data = [5, 3, 8, 1, 9, 2, 7]
print('Top 3 largest:', heapq.nlargest(3, data))  # [9, 8, 7]
print('Top 3 smallest:', heapq.nsmallest(3, data))  # [1, 2, 3]

Patrones prácticos de heaps en entrevistas

Los heaps resuelven una familia de problemas de entrevistas mediante un patrón común: mantener una cola de prioridad de k candidatos mientras se procesan en streaming n elementos. Los elementos más frecuentes, los k puntos más cercanos al origen y la planificación de tareas utilizan este patrón. Reconózcalo cuando vea: «dado un flujo de n elementos, mantenga los k mejores»; esto siempre requiere un heap de tamaño k, con un tiempo total de O(n log k).

import heapq

# Top-K closest points to origin using a max-heap of size k
def k_closest(points, k):
    # Use max-heap (negate distance) of size k
    heap = []
    for x, y in points:
        dist = -(x*x + y*y)  # negate for max-heap
        heapq.heappush(heap, (dist, x, y))
        if len(heap) > k:
            heapq.heappop(heap)  # remove farthest
    return [[x, y] for _, x, y in heap]

points = [[1,3], [-2,2], [5,8], [0,1]]
print(k_closest(points, 2))  # 2 closest to origin

Ventajas y desventajas de un heap frente a un array ordenado

Elija un heap cuando solo necesite acceder repetidamente al mínimo o al máximo y la colección cambie dinámicamente. Elija un array ordenado cuando necesite acceso aleatorio por índice o consultas de rango. La desventaja del heap es que buscar elementos arbitrarios requiere O(n); su ventaja es que insertar y eliminar requieren O(log n), mientras que acceder al mínimo o al máximo requiere O(1). Un array ordenado permite insertar en O(n), pero buscar en O(log n) mediante búsqueda binaria.

# Trade-off comparison:
# Structure     | insert  | delete_min | search | range_query
# --------------|---------|------------|--------|------------
# Min-heap      | O(logn) | O(logn)    | O(n)   | O(n)
# Sorted array  | O(n)    | O(n)       | O(logn)| O(logn+k)
# BST (balanced)| O(logn) | O(logn)    | O(logn)| O(logn+k)
# Hash map      | O(1)    | O(1)       | O(1)   | O(n)

# Interview heuristic:
# 'Find minimum repeatedly from dynamic collection' -> HEAP
# 'Binary search or range query' -> sorted array or BST
# 'Fast lookup by key' -> hash map
print('Heap = dynamic collection with priority access')

Comprobación rápida

Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.

Resumen de la lección

En esta lección ha aprendido: la propiedad de heap y la estructura de árbol binario completo; la representación mediante un array, con las fórmulas de los índices de padres e hijos; y sift-up y sift-down como componentes básicos de todas las operaciones de heap, incluida la construcción O(n) de Floyd. A continuación implementaremos heapify y exploraremos el módulo heapq de Python.

Preguntas frecuentes

¿La lección «Propiedad del heap y representación en array» es gratis?

Sí — el texto completo de «Propiedad del heap y representación en array» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.

¿Qué aprenderé en «Propiedad del heap y representación en array»?

Comprenda la estructura de árbol binario completo almacenada como array, derive las fórmulas de índices de padres e hijos y visualice las operaciones sift-up y sift-down. Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.

¿Necesito experiencia previa para empezar Coding Interview Prep?

No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 1 de 4.

¿Cuánto tiempo toma la lección «Propiedad del heap y representación en array»?

La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.

¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?

Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.

Todas las lecciones de este curso

  1. Propiedad del heap y representación en array
  2. Heapify, push y pop desde cero
  3. heapq de Python y trucos para max-heap
  4. Mediana de un flujo de datos y combinación k-way
← Volver a Coding Interview Prep