Binomial min heap — insert, meld and extract

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <errno.h>

stdio.h supplies terminal input/output. stdlib.h declares conversion and allocation functions. string.h supplies string and memory utilities. ctype.h supplies isspace, and errno.h supplies conversion error reporting. Headers declare facilities; including them does not execute an operation.

/* Read one entire token; reject malformed, oversized and out-of-range input. */
int readToken(char text[], size_t capacity) {
    int ch; size_t used = 0; int fits = 1;

readToken receives a writable buffer and its capacity. ch is int so it can represent EOF as well as input characters. used counts stored characters, and fits starts as a success flag. One slot must remain for the null terminator.

    while ((ch = getchar()) != EOF && isspace((unsigned char)ch)) { }
    if (ch == EOF) return 0;

Read until a non-whitespace character appears. The unsigned-char cast supplies an allowed value to isspace. Return 0 if EOF arrives before a token begins.

    do {
        if (ch == 0) fits = 0;
        if (used + 1 < capacity) text[used++] = (char)ch;
        else fits = 0;

The do body handles the character already read. An embedded zero byte marks the token invalid. Store a character only while there is room for it and a null terminator; otherwise clear fits. Continue reading even after the buffer fills.

        ch = getchar();
    } while (ch != EOF && !isspace((unsigned char)ch));
    text[used] = '\0';
    return fits;
}

Read through the next whitespace or EOF, add a null character after the stored prefix, then return fits. A too-long token returns 0 rather than pretending that its stored prefix is the complete token.

int readInt(int *value) {
    char token[64], *end;
    if (!readToken(token, sizeof token)) return 0;

value is an output address. A 64-slot local buffer receives the token; a failed token read returns 0 before attempting conversion.

    errno = 0; long result = strtol(token, &end, 10);
    if (errno || end == token || *end || result < -1000000 || result > 1000000) return 0;

Reset errno before strtol. &end receives the stopping address. Reject conversion errors, no converted digits, leftover characters, or values outside -1,000,000 to 1,000,000. Thus 12x is not accepted as the integer 12.

    *value = (int)result; return 1;
}
int invalid(void) { puts("Invalid or incomplete input."); return 1; }

Store a validated integer through *value and return 1 from readInt. invalid is a separate helper that prints the error and returns 1 as main’s failure status; the same number has different roles in these two function contracts.

#define MAX_N 100
typedef struct Node { int key, degree; struct Node *parent, *child, *sibling; } Node;

Each node stores key and degree, plus parent, first-child and sibling links. The driver limits the two heaps together to 100 keys. This is a min-heap example, unlike the separate max-oriented binary heap.

/* Merge two degree-sorted root lists; consolidation is a separate step. */
Node *mergeRoots(Node *a, Node *b) {
    Node *head = NULL, **tail = &head;

head starts empty and tail points to the pointer slot where the next root should be linked. A pointer-to-pointer allows the same assignment to fill either head or a later sibling link.

    while (a && b) {
        if (a->degree <= b->degree) { *tail = a; a = a->sibling; }
        else { *tail = b; b = b->sibling; }
        tail = &(*tail)->sibling;
    }
    *tail = a ? a : b; return head;
}

Choose the root with the smaller degree, advance that list, then move tail to the selected root’s sibling slot. Attach the remaining list when one runs out. Equal-degree consolidation is deliberately a separate step.

void linkTree(Node *child, Node *parent) {
    child->parent = parent; child->sibling = parent->child; parent->child = child; ++parent->degree;
}

Make child identify its new parent, insert it at the front of the parent’s child list, and increment the parent’s degree. The caller chooses the smaller-key root as parent to preserve min-heap order.

Node *meld(Node *a, Node *b) {
    Node *head = mergeRoots(a,b); if (!head) return NULL;
    Node *previous = NULL, *current = head, *next = current->sibling;

Return NULL for two empty inputs. Otherwise previous, current and next identify neighbouring roots so consolidation can repair the root-list links.

    while (next) {
        if (current->degree != next->degree ||
            (next->sibling && next->sibling->degree == current->degree)) {
            previous = current; current = next;

Different degrees remain separate. When three consecutive roots have the same degree, advance first rather than linking the first pair immediately; this handles the carry-like consolidation order correctly.

        } else if (current->key <= next->key) {
            current->sibling = next->sibling; linkTree(next,current);

Remove next from the root list and link it under current. The merged tree now has one higher degree; later iterations may need to combine it again.

        } else {
            if (previous) previous->sibling = next; else head = next;
            linkTree(current,next); current = next;
        }

Reconnect previous, or the heap head, to next. Link current under next and make next the new current root. This preserves the root list while choosing the min-ordered parent.

        next = current->sibling;
    }
    return head;
}

Refresh next after every possible link. When no next root remains, return the consolidated head.

int insert(Node **heap, int key) {
    Node *p = malloc(sizeof *p); if (!p) return 0;
    p->key = key; p->degree = 0; p->parent = p->child = p->sibling = NULL;
    *heap = meld(*heap,p); return 1;
}

Allocate and initialise a degree-zero node with no links. On failure return 0 without altering the heap. On success meld it into the caller’s root list and store the returned head through Node **heap.

Node *minimum(Node *heap) {
    Node *best = heap;
    for (Node *p = heap; p; p = p->sibling) if (p->key < best->key) best = p;
    return best;
}

The minimum of each min-ordered tree is its root, so inspect only the root sibling list. For an empty heap the loop runs zero times and returns NULL; no null best pointer is dereferenced.

int extractMin(Node **heap, int *value) {
    if (!*heap) return 0;
    Node *best = minimum(*heap), *previous = NULL, *p = *heap;
    while (p != best) { previous = p; p = p->sibling; }
    if (previous) previous->sibling = best->sibling; else *heap = best->sibling;

Reject an empty heap. Locate the best root and its predecessor, then bypass it in the root list or update the heap head when it was first.

    Node *children = NULL; p = best->child;
    while (p) {
        Node *next = p->sibling; p->parent = NULL; p->sibling = children; children = p; p = next;
    }

Detach each child from its old parent, clear its parent link and prepend it to children. The reversal changes descending child-degree order into the ascending root-degree order required by meld.

    *value = best->key; free(best); *heap = meld(*heap,children); return 1;
}

Copy best->key before free. Meld the remaining roots with the reversed child roots and retain the new head. Return success after the output value is assigned.

void display(const Node *p, int depth) {
    while (p) {
        printf("Depth %d: key=%d degree=%d\n",depth,p->key,p->degree);
        display(p->child,depth + 1); p = p->sibling;
    }
}

Print each node’s key and degree, recurse into its children one depth lower, then advance to its sibling. Depth describes structure, not sorted key order.

void destroy(Node *p) {
    while (p) { Node *next = p->sibling; destroy(p->child); free(p); p = next; }
}

Save the next sibling before recursively destroying children and freeing the current node. This prevents reading a next link from released storage.

/* Two heaps, IDs 1 and 2. Commands:
   1 id key: insert, 2 id: extract min, 3 id: minimum, 4 id: structure,
   5 destination source: meld and empty source, 0: exit. Total capacity 100. */
int main(void) {
    Node *heaps[2] = {NULL,NULL}; int counts[2] = {0,0}, command, id, key, status = 1;

The command comment specifies heap IDs 1 and 2 and a combined capacity. Both root lists and counts begin empty. status starts as failure until explicit command 0 is read.

    while (readInt(&command)) {
        if (!command) { status = 0; break; }
        if (!readInt(&id) || id < 1 || id > 2) break;
        --id;

Command 0 records success and leaves the loop. Other commands require ID 1 or 2; subtract one only after validation to obtain array index 0 or 1.

        if (command == 1) {
            if (!readInt(&key)) break;
            if (counts[0] + counts[1] == MAX_N) puts("Heaps are full.");
            else if (insert(&heaps[id],key)) { ++counts[id]; puts("Inserted."); }
            else puts("Allocation failed; heap unchanged.");
        } else if (command == 2) {
            if (extractMin(&heaps[id],&key)) { --counts[id]; printf("Extracted: %d\n",key); }
            else puts("Empty heap.");

Insertion reads a key, checks the combined count and increments only on success. Extraction decrements only after extractMin returns an item. Empty or failed operations do not change the count.

        } else if (command == 3) {
            Node *p = minimum(heaps[id]); if (p) printf("Minimum: %d\n",p->key); else puts("Empty heap.");
        } else if (command == 4) {
            if (heaps[id]) display(heaps[id],0); else puts("Empty heap.");

minimum may return NULL, so inspect p before printing its key. Structure display likewise checks whether the selected heap is empty.

        } else if (command == 5) {
            int source; if (!readInt(&source) || source < 1 || source > 2 || source - 1 == id) break;
            --source; heaps[id] = meld(heaps[id],heaps[source]); heaps[source] = NULL;
            counts[id] += counts[source]; counts[source] = 0; puts("Meld complete; source empty.");

Validate a distinct source heap ID, convert it to an index, meld into the destination and set the source head to NULL. Transfer its count too. Emptying the source prevents both heap variables from owning the same nodes.

        } else break;
    }
    destroy(heaps[0]); destroy(heaps[1]); return status ? invalid() : 0;
}

An unsupported command or failed read leaves failure status. After the loop destroy both heap lists and return either the recorded success or the standard error.