Heaps & Scheduling

Heaps, timers, scheduling, and wrap-safe time

An array-backed binary min-heap stores the next deadline at index zero and supports bounded O(log n) insertion/removal without pointers. Correct timer systems also require deterministic tie-breaking, cancellation bookkeeping, and a documented modular-time comparison horizon.

The heap invariant is local: every parent compares no greater than its children. Insert appends then sifts up; pop replaces the root with the last element then sifts down. The array is compact, but it is not sorted—only the minimum is guaranteed at the root.

Equal deadlines need a total comparator such as (deadline,insertion_sequence,id). Without deterministic tie-breaking, tests and callback order may vary. Cancel-by-ID requires an index map updated during every swap; stale reverse mappings are a classic heap corruption bug.

Unsigned tick subtraction can compare wrapping time when all relevant distances stay within half the counter range. This is a bounded modular-order technique, not a total order over arbitrary historical timestamps. State the horizon explicitly.

Patterns and when they apply

binary min-heap

Timers, deadlines, running top-k. Cost: O(log n) mutation, O(1) peek. Avoid when: Assuming array iteration is sorted.

ready bitmap

Small fixed priority set with bit-scan/CLZ. Cost: Constant storage and selection. Avoid when: Undefined zero-input intrinsic behavior.

token bucket

Bounded average rate with configurable burst. Cost: Fixed-point/time arithmetic. Avoid when: Unbounded token accumulation or wrap bugs.

Insert deadline 3

1. Append 3 at the heap's logical end.
2. Compare it with its parent.
3. Swap while the parent is greater.
4. Stop at root or when parent<=child.

Only the ancestor path changes, so insertion takes at most heap height O(log n).

Checklist

• What is the capacity-full status?
• How are equal keys ordered?
• Does every swap update auxiliary maps?
• What happens at tick wrap?
• Is the comparator transitive?

Medium - Fixed-Capacity Timer Heap

The timer subsystem of every RTOS and every bare-metal scheduler: which of N pending timers expires next.

Implement a min-heap of deadline/callback pairs with deterministic tie-breaking and no allocation. Support add, peek, and pop.

Fixed timer min-heap

Caller provides capacity. Earlier deadline wins; equal deadlines use lower sequence for deterministic FIFO order.

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

typedef struct { uint32_t deadline,sequence; uint16_t id; } timer_t;
typedef struct { timer_t *items; size_t size,capacity; } timer_heap_t;
static bool before(timer_t a,timer_t b){return a.deadline<b.deadline || (a.deadline==b.deadline && a.sequence<b.sequence);}
static void swap(timer_t *a,timer_t *b){timer_t t=*a;*a=*b;*b=t;}

bool timer_push(timer_heap_t *h,timer_t value){
    if(!h||!h->items||h->size==h->capacity)return false;
    size_t i=h->size++; h->items[i]=value;
    while(i>0u){size_t p=(i-1u)/2u;if(!before(h->items[i],h->items[p]))break;swap(&h->items[i],&h->items[p]);i=p;}
    return true;
}

bool timer_pop(timer_heap_t *h,timer_t *out){
    if(!h||!out||h->size==0u)return false;
    *out=h->items[0]; h->items[0]=h->items[--h->size]; size_t p=0u;
    for(;;){size_t l=2u*p+1u,r=l+1u,b=p;if(l<h->size&&before(h->items[l],h->items[b]))b=l;if(r<h->size&&before(h->items[r],h->items[b]))b=r;if(b==p)break;swap(&h->items[p],&h->items[b]);p=b;}
    return true;
}

• The comparator defines a total deterministic order.
• Push repairs only the new node's ancestor path.
• Pop repairs only the replacement root's descendant path.

Cases the tests must cover

• ascending/descending insertion
• equal deadline sequence order
• capacity full
• pop empty
• heap invariant after every operation

How it gets written wrong

• Plain unsigned deadline comparison is not wrap-safe; use a documented horizon comparator when deadlines wrap.
• Cancelable heaps must update ID→index maps on every swap.

Hard - Cancelable Timer Queue

Cancelling a pending timeout when the awaited event arrives first, which is what every request with a retry deadline does.

Extend the timer heap so a timer ID can be canceled in O(log n). Keep an ID-to-index table consistent during every swap.

O(log n) timer cancel with an ID-to-index map

timer_cancel removes the timer with the given ID in O(log n): the id->slot table locates the entry in O(1), the hole is refilled by sift-down/up, and every swap keeps the table consistent. Returns false for an unknown ID.

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

#define TIMER_CAP 16u
#define TIMER_ID_INVALID 0xFFFFu

typedef struct { uint32_t deadline; uint16_t id; } timer_t;

typedef struct {
    timer_t items[TIMER_CAP];
    size_t count;
    uint8_t slot_of[TIMER_CAP];   /* id -> heap index (ids dense 0..CAP-1) */
} timer_heap_t;

static bool earlier(const timer_t *a, const timer_t *b) {
    /* Wrap-safe compare, then deterministic tie-break by id. */
    if (a->deadline == b->deadline) return a->id < b->id;
    return (int32_t)(a->deadline - b->deadline) < 0;
}

static void swap_slots(timer_heap_t *h, size_t i, size_t j) {
    timer_t tmp = h->items[i];
    h->items[i] = h->items[j];
    h->items[j] = tmp;
    /* THE invariant: after every swap the map follows the timers. */
    h->slot_of[h->items[i].id] = (uint8_t)i;
    h->slot_of[h->items[j].id] = (uint8_t)j;
}

static void sift_up(timer_heap_t *h, size_t i) {
    while (i > 0u) {
        size_t parent = (i - 1u) / 2u;
        if (!earlier(&h->items[i], &h->items[parent])) break;
        swap_slots(h, i, parent);
        i = parent;
    }
}

static void sift_down(timer_heap_t *h, size_t i) {
    for (;;) {
        size_t l = 2u * i + 1u, r = l + 1u, best = i;
        if (l < h->count && earlier(&h->items[l], &h->items[best])) best = l;
        if (r < h->count && earlier(&h->items[r], &h->items[best])) best = r;
        if (best == i) break;
        swap_slots(h, i, best);
        i = best;
    }
}

bool timer_cancel(timer_heap_t *h, uint16_t id) {
    if (h == NULL || id >= TIMER_CAP) return false;
    size_t i = h->slot_of[id];
    if (i >= h->count || h->items[i].id != id) return false;  /* not present */
    /* Move the last element into the hole, then restore the heap order
       in whichever direction the replacement violates. */
    h->count--;
    if (i != h->count) {
        h->items[i] = h->items[h->count];
        h->slot_of[h->items[i].id] = (uint8_t)i;
        sift_down(h, i);
        sift_up(h, i);          /* at most one of the two sifts does work */
    }
    h->slot_of[id] = 0u;        /* optional: stale value is guarded by the
                                   items[i].id != id membership check */
    return true;
}

• A bare heap answers 'what fires next?' in O(1) but 'cancel timer #7' in O(n) — you must find it first. The id->index side table removes the scan: lookup is O(1), removal is the standard delete-with-replacement, O(log n).
• The entire design hinges on one invariant: slot_of[id] is the heap index of that timer, updated inside swap_slots so it can never drift from the array. Put the update in the one place all movement funnels through.
• Deleting index i moves the last element into the hole. That replacement might be earlier than its new parent or later than its new children — running sift_down then sift_up covers both; one of them always exits immediately.
• Membership is double-checked (i < count AND items[i].id == id) so a cancel for an already-fired timer cannot delete an unrelated entry that reused the slot.
• The wrap-safe deadline compare (int32_t)(a-b) < 0 and the id tie-break keep pop order deterministic even when two timers share a deadline.

Cases the tests must cover

• Cancel the root, a leaf, and a middle node; heap order verified after each
• Cancel every timer in random order from a full heap — count reaches 0 with a consistent map
• Cancel an unknown/fired id returns false and changes nothing
• Two timers with equal deadlines: cancel removes exactly the requested id
• Add after cancel reuses the freed slot and keeps the map correct

How it gets written wrong

• Updating the map in add/pop but forgetting one swap path inside cancel — the classic desync that surfaces days later as cancelling the wrong timer.
• Searching the heap linearly for the id: correct but O(n), which misses the whole point of the table.
• Deleting by swapping with the last element and only sifting down; if the replacement is earlier than its parent the heap is broken.

Easy - Highest Ready Priority

Choosing the highest-priority ready task in constant time - the core of the scheduler on nearly every small RTOS.

Represent 32 RTOS ready priorities in a bitmap and return the highest set priority without looping when a CLZ intrinsic is available.

Highest set priority via CLZ

Returns the highest set priority (bit 31 = priority 31 highest) from a 32-bit ready bitmap, or -1 when no task is ready. O(1) with a CLZ intrinsic, defined without it.

#include <stdint.h>

int highest_ready(uint32_t ready_bitmap) {
    if (ready_bitmap == 0u) return -1;    /* no ready task */
#if defined(__GNUC__) || defined(__clang__)
    /* CLZ maps directly to one instruction on Cortex-M3+.
       Top set bit index = 31 - clz. */
    return 31 - __builtin_clz(ready_bitmap);
#else
    /* Portable fallback: unrolled binary search over halves. */
    int pos = 0;
    uint32_t v = ready_bitmap;
    if (v & 0xFFFF0000u) { pos += 16; v >>= 16; }
    if (v & 0xFF00u)     { pos += 8;  v >>= 8;  }
    if (v & 0xF0u)       { pos += 4;  v >>= 4;  }
    if (v & 0xCu)        { pos += 2;  v >>= 2;  }
    if (v & 0x2u)        { pos += 1; }
    return pos;
#endif
}

• An RTOS with 32 priorities keeps one bit per priority; scheduling the highest-priority ready task means finding the most significant set bit — the exact job of the CLZ (count leading zeros) instruction on Cortex-M3/M4/M7.
• highest = 31 - clz. On an M4 this is one CLZ and one RSB: constant time, a couple of cycles, no loop — that is why bitmap schedulers (uC/OS, FreeRTOS with port optimized) scale to any priority count.
• The portable fallback does a binary search over bit halves: test the top 16 bits, then 8, 4, 2, 1 — five constant-time tests instead of a 32-iteration scan.
• The zero bitmap is rejected up front: __builtin_clz(0) is undefined, and '-1' for 'no ready task' is the scheduler's idle-task trigger.

Cases the tests must cover

• 0x00000001 → 0; 0x80000000 → 31 (both ends)
• Single bits 1..30 all return their index
• Multiple bits set → the highest index wins
• 0 → -1, and the CLZ path is never reached with 0
• Fallback and builtin paths agree on 10000 random bitmaps

How it gets written wrong

• Calling __builtin_clz(0) — undefined result; guard first.
• Looping from bit 0 upward looking for the highest: 32 iterations of jitter in the hottest path of the scheduler.
• Off-by-one between '31 - clz' and '32 - clz'; test bit 0 and bit 31 explicitly.

Medium - Wrap-Safe Deadline Ordering

Comparing deadlines against a free-running tick counter that wraps - at 1 kHz a 32-bit tick wraps after 49.7 days, and at 1 MHz after 71 minutes.

Compare 32-bit tick deadlines correctly across counter wrap, assuming no deadline is more than 2^31-1 ticks away.

Wrap-safe tick comparison (signed difference)

Returns true when deadline a is earlier than deadline b, correct across a 32-bit tick wrap, provided no two compared deadlines are more than 2^31 - 1 ticks apart.

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

bool time_before(uint32_t a, uint32_t b) {
    /* Unsigned subtraction wraps mod 2^32 (defined); the cast to int32_t
       then reinterprets the distance as signed. If a is 'behind' b within
       half the counter range, the difference is negative. */
    return (int32_t)(a - b) < 0;
}

/* Companion: ticks elapsed from start to now, correct across the same wrap.
   (uint32_t)(now - start) is the true duration whenever the real elapsed
   time fits in 32 bits, even if 'now' wrapped past zero. */
uint32_t time_elapsed(uint32_t start, uint32_t now) {
    return now - start;
}

/* Convenience: has 'deadline' been reached at time 'now'? */
bool time_expired(uint32_t now, uint32_t deadline) {
    return (int32_t)(now - deadline) >= 0;
}

• The whole trick is one line. Suppose the tick counter is 0xFFFFFFFE and a deadline is 3 (post-wrap). Unsigned 0xFFFFFFFE - 3 wraps to a huge number, but reinterpreted as int32_t it is -5: 'a is 5 ticks before b'. Correct across the wrap.
• It works because unsigned subtraction is modular arithmetic: (a - b) mod 2^32 is the true distance on a circle. The signed cast picks the shorter direction, valid as long as real distances stay under half the circle (2^31).
• The 2^31-1 range limit is the price: at 1 kHz ticks that is still 24.8 days of lookahead, far beyond any sane timer horizon. Document it at the API.
• The same pattern gives wrap-safe elapsed time: (uint32_t)(now - start) is always the correct duration even when now wrapped past zero.
• Linux uses exactly this: time_before(a,b) in the kernel is (int32_t)(a - b) < 0, jiffies wrap and all.

Cases the tests must cover

• time_before(0xFFFFFFFE, 3) == true (deadline before wrap, target after)
• time_before(3, 0xFFFFFFFE) == false
• time_before(100, 200) == true in the no-wrap region
• a == b returns false (not strictly before)
• Elapsed: (now - start) across a wrap equals the real tick count

How it gets written wrong

• Comparing a < b directly: every timer set near the wrap fires immediately or 49 days late.
• Exceeding the 2^31 range: the comparison silently flips direction.
• Using (int32_t)a - (int32_t)b instead of (int32_t)(a - b) — signed overflow of the subtraction itself is UB; subtract unsigned first.

Medium - Token-Bucket Rate Limiter

Limiting how often something expensive may happen: radio transmissions under a duty-cycle regulation, log writes to flash with finite endurance, retries against a server.

Implement a fixed-point token bucket for CAN or telemetry messages. Refill from wrap-safe ticks and cap accumulated tokens.

Fixed-point token bucket rate limiter

Allows a message of cost tokens when the bucket holds enough, refilling at a fixed-point rate from wrap-safe elapsed ticks. Tokens cap at burst capacity. Returns false (bucket unchanged besides refill) when the cost exceeds the balance.

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

typedef struct {
    uint32_t tokens_q16;   /* balance in Q16.16 fixed point */
    uint32_t rate_q16;     /* tokens added per tick, Q16.16 */
    uint32_t burst;        /* max whole tokens the bucket can hold */
    uint32_t last_tick;    /* last refill timestamp */
} bucket_t;

void bucket_init(bucket_t *b, uint32_t rate_q16, uint32_t burst, uint32_t now) {
    b->tokens_q16 = burst << 16;   /* start full */
    b->rate_q16 = rate_q16;
    b->burst = burst;
    b->last_tick = now;
}

static void refill(bucket_t *b, uint32_t now) {
    uint32_t elapsed = now - b->last_tick;      /* wrap-safe unsigned diff */
    if (elapsed == 0u) return;
    b->last_tick = now;
    uint64_t add = (uint64_t)elapsed * b->rate_q16;   /* 64-bit: no wrap */
    uint64_t total = (uint64_t)b->tokens_q16 + add;
    uint64_t cap = (uint64_t)b->burst << 16;
    b->tokens_q16 = (uint32_t)(total > cap ? cap : total);  /* cap the burst */
}

bool rate_allow(bucket_t *b, uint32_t now, uint32_t cost) {
    if (b == NULL) return false;
    refill(b, now);
    uint64_t need = (uint64_t)cost << 16;
    if ((uint64_t)b->tokens_q16 < need) return false;  /* not enough budget */
    b->tokens_q16 -= (uint32_t)need;
    return true;
}

• A token bucket answers 'may I send now?' for bursty protocols like CAN or telemetry: tokens drip in at a fixed rate, each message spends tokens, and the burst cap bounds how much credit can accumulate while idle.
• Fixed-point Q16.16 (1.0 token = 65536) lets you express fractional rates like 0.5 tokens per tick with pure integers — no float library, deterministic on every core.
• Refill is lazy: nothing ticks in the background; each call computes elapsed ticks (wrap-safe unsigned subtraction) and tops up. One less timer, one less ISR.
• The accumulation multiply runs in uint64_t: elapsed can be huge after a long sleep, and elapsed * rate must not wrap before the cap is applied.
• A rejected message only costs the refill — the balance is not debited — so a too-expensive message waits for budget instead of going negative.

Cases the tests must cover

• Full bucket allows burst messages, then rejects once drained
• Idle period refills only up to the burst cap, never beyond
• Fractional rate (0.5/tick) grants one token every two ticks
• Tick wrap between calls still refills the correct elapsed count
• cost 0 always allowed; cost > burst never allowed

How it gets written wrong

• 32-bit elapsed * rate overflow before capping — the bucket magically refills to garbage after long idle.
• Refilling per tick in an ISR instead of lazily: wasted cycles and a shared-state race with the consumer.
• Letting tokens accumulate without a cap; a quiet device then bursts thousands of messages, which is exactly what the limiter exists to prevent.

Medium - Running Kth Largest Sample

Maintaining a percentile over a stream without storing it: the kth largest current reading for outlier rejection or adaptive thresholds.

Process a sample stream and report the kth largest value seen so far using a caller-owned fixed min-heap of k entries.

Running kth largest with a fixed min-heap

Feeds samples into a caller-owned min-heap of k entries; once k samples were seen, *kth reports the kth largest so far and the function returns true. Before that it returns false. Samples that cannot enter the top k are discarded in O(1).

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

typedef struct {
    int16_t *heap;   /* caller storage, capacity k, used as a min-heap */
    size_t k;
    size_t size;     /* entries used so far (<= k) */
} kth_tracker_t;

void kth_init(kth_tracker_t *t, int16_t *storage, size_t k) {
    t->heap = storage;
    t->k = k;
    t->size = 0u;
}

static void sift_up(kth_tracker_t *t, size_t i) {
    while (i > 0u) {
        size_t parent = (i - 1u) / 2u;
        if (t->heap[parent] <= t->heap[i]) break;   /* min-heap: parent <= child */
        int16_t tmp = t->heap[parent];
        t->heap[parent] = t->heap[i];
        t->heap[i] = tmp;
        i = parent;
    }
}

static void sift_down(kth_tracker_t *t, size_t i) {
    for (;;) {
        size_t l = 2u * i + 1u, r = l + 1u, best = i;
        if (l < t->size && t->heap[l] < t->heap[best]) best = l;
        if (r < t->size && t->heap[r] < t->heap[best]) best = r;
        if (best == i) break;
        int16_t tmp = t->heap[best];
        t->heap[best] = t->heap[i];
        t->heap[i] = tmp;
        i = best;
    }
}

bool kth_update(kth_tracker_t *t, int16_t sample, int16_t *kth) {
    if (t == NULL || t->k == 0u) return false;
    if (t->size < t->k) {
        t->heap[t->size] = sample;      /* still filling: always accept */
        t->size++;
        sift_up(t, t->size - 1u);
    } else if (sample > t->heap[0]) {
        t->heap[0] = sample;            /* evict smallest of the top k */
        sift_down(t, 0u);
    } /* else: cannot enter the top k, discard without touching the heap */
    if (t->size == t->k && kth != NULL) {
        *kth = t->heap[0];              /* root = smallest of the k largest */
        return true;
    }
    return false;
}

• To know the kth largest of a stream you never need the whole stream — just the k largest so far, and of those only the smallest matters for comparison. A min-heap of size k puts that decision value at the root in O(1).
• While filling (size < k) every sample joins. Once full, a new sample only matters if it beats the root; replacing the root and sifting down costs O(log k), and rejects cost one compare.
• The root invariant is the whole trick: heap[0] is the smallest of the k largest, which is by definition the kth largest value seen.
• Memory is exactly k int16s of caller storage — the pattern for top-k telemetry on devices where the stream is millions of samples and RAM is kilobytes.

Cases the tests must cover

• Stream [4,9,1,7,12,3] with k=3 → after each: ?, ?, 4, 7, 9, 7
• Ascending stream k=1 → always the latest sample (running max)
• Fewer than k samples returns false, no kth written
• All samples equal → kth equals that value
• Duplicates around the boundary are counted with multiplicity

How it gets written wrong

• Using a max-heap: then the root is the largest and you cannot cheaply reject middling samples.
• Comparing new samples against the last inserted or the median — only the root decides.
• Reporting kth before k samples arrived; the heap is full of the only data and the 'kth largest' is meaningless.

Hard - Merge K Sorted Sensor Runs

Merging several sorted sensor logs into one time-ordered stream - combining per-peripheral capture buffers into a single trace for export.

Merge k sorted arrays into an output buffer with a fixed heap containing at most one cursor per input run.

K-way merge with one heap cursor per run

Merges k sorted int16 runs into out (cap-limited) using a caller-provided heap array of k nodes holding at most one cursor per run. Returns samples written. Stops cleanly when out fills, even mid-merge.

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

typedef struct { const int16_t *data; size_t len; } run_t;
typedef struct { int16_t value; uint16_t run; } heap_node_t;

static void sift_up(heap_node_t *h, size_t i) {
    while (i > 0u) {
        size_t p = (i - 1u) / 2u;
        if (h[p].value < h[i].value ||
            (h[p].value == h[i].value && h[p].run <= h[i].run)) break;
        heap_node_t tmp = h[p]; h[p] = h[i]; h[i] = tmp;
        i = p;
    }
}

static void sift_down(heap_node_t *h, size_t n, size_t i) {
    for (;;) {
        size_t l = 2u * i + 1u, r = l + 1u, best = i;
        if (l < n && (h[l].value < h[best].value ||
            (h[l].value == h[best].value && h[l].run < h[best].run))) best = l;
        if (r < n && (h[r].value < h[best].value ||
            (h[r].value == h[best].value && h[r].run < h[best].run))) best = r;
        if (best == i) break;
        heap_node_t tmp = h[best]; h[best] = h[i]; h[i] = tmp;
        i = best;
    }
}

size_t merge_runs(const run_t *runs, size_t k, int16_t *out, size_t cap,
                  heap_node_t *heap) {
    if (runs == NULL || (k > 0u && heap == NULL)) return 0u;
    size_t heap_n = 0u;
    size_t cursors[64];   /* one read cursor per run; k <= 64 by contract */
    if (k > 64u) return 0u;
    /* Seed: one node per non-empty run. */
    for (size_t r = 0u; r < k; r++) {
        cursors[r] = 0u;
        if (runs[r].len > 0u) {
            heap[heap_n].value = runs[r].data[0];
            heap[heap_n].run = (uint16_t)r;
            heap_n++;
            sift_up(heap, heap_n - 1u);
        }
    }
    size_t written = 0u;
    while (heap_n > 0u && written < cap) {
        heap_node_t min = heap[0];          /* globally smallest head */
        out[written++] = min.value;
        size_t r = min.run;
        cursors[r]++;
        if (cursors[r] < runs[r].len) {
            heap[0].value = runs[r].data[cursors[r]];  /* advance same run */
            heap[0].run = (uint16_t)r;
        } else {
            heap[0] = heap[heap_n - 1u];    /* run exhausted: shrink heap */
            heap_n--;
        }
        sift_down(heap, heap_n, 0u);
    }
    return written;
}

• k sorted runs, one globally sorted output. At any moment the next output value is the smallest among the k current heads — a min-heap holding exactly one entry per run answers that in O(1) peek and O(log k) update.
• After emitting a value, only the run it came from advances. If that run has more data its next value replaces the root; otherwise the heap shrinks by one. Either way one sift-down restores order.
• Ties break by run index so equal values from different runs come out in a deterministic order — reproducible output makes test vectors stable.
• Total work is O(n log k) for n total samples: with 8 flash-resident log runs that is 3 heap levels per sample instead of an 8-way linear scan per sample (O(nk)).
• The heap never holds more than k nodes, supplied by the caller — merging gigabytes of sorted runs needs only k entries of RAM.

Cases the tests must cover

• [[1,8],[2,3,9],[4,7]] → 1,2,3,4,7,8,9
• Some runs empty: merge succeeds over the non-empty ones
• cap smaller than total: output is the first cap sorted values
• Duplicate values across runs: stable run-index order, nothing lost
• k = 1 behaves as a straight copy

How it gets written wrong

• Pushing every element of every run into the heap — that is O(n) heap space and defeats the cursor design.
• Forgetting to advance the cursor of the run you just emitted, re-emitting its head forever.
• Unstable tie-breaking producing different output orders between builds with identical input.

Medium - In-Place Heapsort

Sorting in place with a hard worst-case bound and no recursion - the sort you use when the timing must be provable and the stack must not grow.

Sort a fixed array in place: build a max-heap bottom-up, then repeatedly move the maximum to the end. No recursion and no extra buffer.

In-place heapsort

Sorts ascending in place. NULL or n<2 is a tolerated no-op. No recursion, no auxiliary buffer, not stable.

#include <assert.h>
#include <stddef.h>
#include <stdint.h>

static void sift_down(int16_t *a, size_t root, size_t n)
{
    for (;;) {
        size_t child = 2U * root + 1U;
        int16_t t;
        if (child >= n) return;
        if ((child + 1U < n) && (a[child] < a[child + 1U])) ++child;
        if (a[root] >= a[child]) return;
        t = a[root]; a[root] = a[child]; a[child] = t;
        root = child;
    }
}

void heap_sort(int16_t *a, size_t n)
{
    size_t i;
    if ((a == NULL) || (n < 2U)) return;
    for (i = n / 2U; i-- > 0U; ) sift_down(a, i, n);       /* build max-heap */
    for (i = n - 1U; i > 0U; --i) {
        int16_t t = a[0]; a[0] = a[i]; a[i] = t;           /* max to the end */
        sift_down(a, 0U, i);
    }
}

int main(void)
{
    int16_t a[] = { 5, -2, 9, 0, 9, -7, 3 };
    size_t i;
    heap_sort(a, 7U);
    for (i = 1U; i < 7U; ++i) assert(a[i - 1U] <= a[i]);
    assert(a[0] == -7 && a[6] == 9);
    heap_sort(NULL, 0U);
    return 0;
}

• Building the heap bottom-up from n/2 down is O(n), not O(n log n).
• i-- > 0 on size_t iterates n/2..0 without signed indices or underflow.
• After each swap the unsorted prefix [0,i) is a heap again after one sift.

Cases the tests must cover

• duplicates and negatives sorted
• already-sorted input
• NULL/empty no-op
• single element unchanged
• reverse-sorted input sorted

How it gets written wrong

• Heapsort is NOT stable: equal keys may reorder; use a key+sequence comparator if order matters.
• 2*root+1 overflows size_t only near SIZE_MAX; impossible for real buffers.

More in Embedded DSA

• The WorkbenchA complete embedded-first DSA course with theory, 80 challenges, complete C11 implementations, visual traces, mastery tracking, interview drills, and a constraint-driven firmware design arena.
• Arrays & WindowsTwo pointers, sliding windows, in-place compaction and streaming filters over sample buffers. Twelve problems with complete C11 solutions, complexity targets and edge-case tests.
• Search & LookupBinary search that actually terminates, lookup tables, perfect hashing and command dispatch. Eleven problems on getting a bounded answer out of a table without a heap allocation in sight.
• Lists, Pools & ArenasIntrusive linked lists, fixed-block pools, arena allocators and why malloc is banned in most firmware. Ten problems on owning memory with a bound you can prove before the board ships.
• Trees, Graphs & StateTries for command tables, union-find for connectivity, and state machines that cannot reach an undefined state. Nine problems on structures that encode relationships rather than sequences.
• Parsing & ProtocolsFraming, COBS, incremental parsers and adversarial input. Nine problems on decoding a byte stream from a hostile world without a buffer overflow or an unbounded loop.
• Linked ListsEvery list variant, written for embedded C rather than for a whiteboard: singly and doubly linked, circular lists and sentinels that delete the boundary cases, the intrusive form kernels and firmware actually use, static pools and free lists for systems without malloc, reversal and cycle detection, and an honest account of when an array is the better answer.
• Sorting Under ConstraintWhich sort survives a 512-byte stack and a fixed deadline. Insertion sort for small nearly-sorted windows, heapsort when the worst case must be provable, counting sort for byte keys, and a bounded-depth quicksort - six problems with complete C11 solutions.
• Integer & Fixed-Point MathComputing the right number with no floating-point unit. Q formats, multiply-before-divide, rounding instead of truncating, division by a constant as a multiply and shift, running averages that do not stall, and LFSR jitter for backoff.
• Stacks, Queues & RingsThe ring buffer and the SPSC queue: the two structures every firmware project actually ships. Ownership between an ISR and a main loop, overflow policy, and why the full/empty test is where the bugs are.
• Bits & BytesRegister fields, bit reversal, parity, endianness and portable packet decoding, without invoking undefined behaviour. Seven problems with complete C11 solutions and a step-by-step trace for each.
• Firmware CapstonesSix full-system problems: DMA ownership, wear-levelled persistence, crash-safe logging and proving a design meets its RAM and WCET budget. This is where every earlier stage gets used at once.