Un heap binario en C

El arreglo es el árbol: los hijos de i viven en 2i+1 y 2i+2.

#include <stddef.h>

static void swap(int *a, int *b) {
    int t = *a;
    *a = *b;
    *b = t;
}

void heap_push(int *heap, size_t *n, int value) {
    size_t i = (*n)++;
    heap[i] = value;
    while (i > 0) {
        size_t parent = (i - 1) / 2;
        if (heap[parent] <= heap[i]) {
            break;
        }
        swap(&heap[parent], &heap[i]);
        i = parent;
    }
}

int heap_pop(int *heap, size_t *n) {
    int top = heap[0];
    heap[0] = heap[--(*n)];
    size_t i = 0;
    for (;;) {
        size_t left = 2 * i + 1;
        size_t smallest = i;
        if (left < *n && heap[left] < heap[smallest]) {
            smallest = left;
        }
        if (left + 1 < *n && heap[left + 1] < heap[smallest]) {
            smallest = left + 1;
        }
        if (smallest == i) {
            break;
        }
        swap(&heap[i], &heap[smallest]);
        i = smallest;
    }
    return top;
}

Cómo funciona

1. Hacer push filtra el valor nuevo hacia arriba, rumbo a la raíz.
2. Hacer pop mueve el último valor a la cima y lo filtra hacia abajo.
3. Ambas son logarítmicas, sin un solo puntero.

Palabras clave y builtins usados aquí

• break
• for
• if
• int
• return
• size_t
• static
• void
• while

El intento, en números

Líneas

42

Caracteres a escribir

696

Tokens

271

Ritmo de tres estrellas

105 tpm

Al ritmo de tres estrellas de 105 tokens por minuto, este intento toma unos 155 segundos.

Escribe este fragmento

Paso 4 de 4 en Árboles, tablas y heaps; paso 14 de 20 en Estructuras de datos y algoritmos.

← Anterior Siguiente →