30010：合并多个有序序列

题目

使用最小堆合并多条非递减整数序列，保持每条序列内部的先后顺序。

解析

堆中的一个元素记录 (value, sequence, offset)，表示某条序列当前尚未输出的首元素。弹出后把同一序列的下一个元素放回堆。总长度和容量在任何写入前先验证；堆分配成功后合并过程不再产生可失败操作。

相等键用序列编号和偏移量做次级比较，只是为了得到确定顺序，不会破坏任何一条序列内部的顺序。

答案

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

typedef struct {
    int64_t value;
    size_t sequence;
    size_t offset;
} HeapEntry;

static bool entry_less(HeapEntry left, HeapEntry right) {
    if (left.value != right.value) {
        return left.value < right.value;
    }
    if (left.sequence != right.sequence) {
        return left.sequence < right.sequence;
    }
    return left.offset < right.offset;
}

static void swap_entry(HeapEntry *left, HeapEntry *right) {
    HeapEntry temporary = *left;
    *left = *right;
    *right = temporary;
}

static void sift_up(HeapEntry *heap, size_t index) {
    while (index > 0) {
        size_t parent = (index - 1) / 2;
        if (!entry_less(heap[index], heap[parent])) {
            return;
        }
        swap_entry(&heap[index], &heap[parent]);
        index = parent;
    }
}

static void sift_down(HeapEntry *heap, size_t size, size_t index) {
    for (;;) {
        size_t smallest = index;
        if (index < size / 2) {
            size_t left = index * 2 + 1;
            size_t right = left + 1;
            if (entry_less(heap[left], heap[smallest])) {
                smallest = left;
            }
            if (right < size && entry_less(heap[right], heap[smallest])) {
                smallest = right;
            }
        }
        if (smallest == index) {
            return;
        }
        swap_entry(&heap[index], &heap[smallest]);
        index = smallest;
    }
}

bool merge_sorted_i64(
    const int64_t *const *sequences,
    const size_t *counts,
    size_t sequence_count,
    int64_t *out_items,
    size_t capacity,
    size_t *out_count
) {
    if (out_count == NULL ||
        (sequence_count > 0 && (sequences == NULL || counts == NULL))) {
        return false;
    }
    size_t total = 0;
    for (size_t i = 0; i < sequence_count; ++i) {
        if (counts[i] > 0 && sequences[i] == NULL) {
            return false;
        }
        if (counts[i] > SIZE_MAX - total) {
            return false;
        }
        total += counts[i];
    }
    if (total > capacity || (total > 0 && out_items == NULL)) {
        return false;
    }
    if (sequence_count > SIZE_MAX / sizeof(HeapEntry)) {
        return false;
    }
    HeapEntry *heap = sequence_count == 0
        ? NULL
        : malloc(sequence_count * sizeof *heap);
    if (sequence_count > 0 && heap == NULL) {
        return false;
    }

    size_t heap_size = 0;
    for (size_t i = 0; i < sequence_count; ++i) {
        if (counts[i] > 0) {
            heap[heap_size++] = (HeapEntry){
                sequences[i][0], i, 0
            };
            sift_up(heap, heap_size - 1);
        }
    }

    size_t written = 0;
    while (heap_size > 0) {
        HeapEntry entry = heap[0];
        out_items[written++] = entry.value;
        ++entry.offset;
        if (entry.offset < counts[entry.sequence]) {
            entry.value = sequences[entry.sequence][entry.offset];
            heap[0] = entry;
        } else {
            --heap_size;
            if (heap_size > 0) {
                heap[0] = heap[heap_size];
            }
        }
        if (heap_size > 0) {
            sift_down(heap, heap_size, 0);
        }
    }
    free(heap);
    *out_count = written;
    return true;
}

每个序列至多占据一个堆项，每次输出执行一次 $O(\log k)$ 调整，因此总时间复杂度为 $O(N\log k)$，额外空间为 $O(k)$。