30008：整数小根堆

题目

实现不透明的整数小根堆，支持插入、查看最小值和弹出最小值。

解析

数组下标 i 的孩子是 2*i+1 和 2*i+2。插入先确保有容量，再把新值向上移动；弹出先保存根值，把最后一个元素移到根，再向下移动。两种移动都只交换违反堆序的父子，因此不变式可以局部恢复。

答案

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>

typedef struct IntMinHeap IntMinHeap;

struct IntMinHeap {
    int64_t *items;
    size_t size;
    size_t capacity;
};

IntMinHeap *int_min_heap_create(void) {
    IntMinHeap *heap = malloc(sizeof *heap);
    if (heap == NULL) {
        return NULL;
    }
    heap->items = NULL;
    heap->size = 0;
    heap->capacity = 0;
    return heap;
}

void int_min_heap_destroy(IntMinHeap *heap) {
    if (heap == NULL) {
        return;
    }
    free(heap->items);
    free(heap);
}

static bool heap_reserve(IntMinHeap *heap) {
    size_t maximum = SIZE_MAX / sizeof *heap->items;
    if (heap->size < heap->capacity) {
        return true;
    }
    if (heap->capacity >= maximum) {
        return false;
    }
    size_t next = heap->capacity == 0 ? 8 : heap->capacity;
    if (next > maximum) {
        return false;
    }
    while (next <= heap->size) {
        if (next > maximum / 2) {
            next = maximum;
            break;
        }
        next *= 2;
    }
    if (next <= heap->size) {
        return false;
    }
    int64_t *replacement = realloc(
        heap->items, next * sizeof *replacement
    );
    if (replacement == NULL) {
        return false;
    }
    heap->items = replacement;
    heap->capacity = next;
    return true;
}

static void swap_i64(int64_t *left, int64_t *right) {
    int64_t temporary = *left;
    *left = *right;
    *right = temporary;
}

static void sift_up(IntMinHeap *heap, size_t index) {
    while (index > 0) {
        size_t parent = (index - 1) / 2;
        if (heap->items[parent] <= heap->items[index]) {
            break;
        }
        swap_i64(&heap->items[parent], &heap->items[index]);
        index = parent;
    }
}

static void sift_down(IntMinHeap *heap, size_t index) {
    for (;;) {
        size_t smallest = index;
        if (index < heap->size / 2) {
            size_t left = index * 2 + 1;
            size_t right = left + 1;
            if (heap->items[left] < heap->items[smallest]) {
                smallest = left;
            }
            if (right < heap->size &&
                heap->items[right] < heap->items[smallest]) {
                smallest = right;
            }
        }
        if (smallest == index) {
            return;
        }
        swap_i64(&heap->items[index], &heap->items[smallest]);
        index = smallest;
    }
}

bool int_min_heap_push(IntMinHeap *heap, int64_t value) {
    if (heap == NULL || !heap_reserve(heap)) {
        return false;
    }
    heap->items[heap->size] = value;
    ++heap->size;
    sift_up(heap, heap->size - 1);
    return true;
}

bool int_min_heap_peek(
    const IntMinHeap *heap,
    int64_t *out_value
) {
    if (heap == NULL || out_value == NULL || heap->size == 0) {
        return false;
    }
    *out_value = heap->items[0];
    return true;
}

bool int_min_heap_pop(
    IntMinHeap *heap,
    int64_t *out_value
) {
    if (heap == NULL || out_value == NULL || heap->size == 0) {
        return false;
    }
    int64_t result = heap->items[0];
    --heap->size;
    if (heap->size > 0) {
        heap->items[0] = heap->items[heap->size];
        sift_down(heap, 0);
    }
    *out_value = result;
    return true;
}

size_t int_min_heap_size(const IntMinHeap *heap) {
    return heap == NULL ? 0 : heap->size;
}

push 和 pop 的时间复杂度为 $O(\log n)$，peek 为 $O(1)$；扩容只在真正写入前发生。