Binary max heap — insert 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 CAPACITY 100
int heap[CAPACITY], count = 0;
void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; }

The global array holds up to 100 items and count starts at zero. swap exchanges two integers through their addresses. For a max-heap each parent is at least as large as either child; the entire array is not globally sorted.

int insert(int value) {
    if (count == CAPACITY) return 0;
    int i = count++; heap[i] = value;

If the heap is full, return 0 before a write. Otherwise i is the old count, count increases, and the new value occupies the next position in the complete-tree shape.

    while (i > 0 && heap[(i - 1) / 2] < heap[i]) {
        int parent = (i - 1) / 2; swap(&heap[i],&heap[parent]); i = parent;
    }
    return 1;
}

For a non-root index, its parent is (i - 1) / 2. While the parent is smaller, swap the two and continue from the parent index. Return success after the max-heap order is restored.

int extractMax(int *value) {
    if (!count) return 0;
    *value = heap[0]; heap[0] = heap[--count]; int i = 0;

An empty heap returns failure. Otherwise copy heap[0] through value, decrease count and use the last item to replace the root. For a one-item heap the active count becomes zero and the following sift loop is skipped.

    while (2 * i + 1 < count) {
        int child = 2 * i + 1;
        if (child + 1 < count && heap[child + 1] > heap[child]) ++child;

The left child is 2*i + 1; continue only if it exists. If a right child also exists and is larger, choose that one so the parent can dominate both children after a swap.

        if (heap[i] >= heap[child]) break;
        swap(&heap[i],&heap[child]); i = child;
    }
    return 1;
}

If the current parent is already at least as large as its larger child, stop. Otherwise swap and continue from the child. Return 1 after providing the extracted maximum.

/* 1 value: insert, 2: extract maximum, 3: peek, 4: array display, 0: exit. */
int main(void) {
    int command, value;
    while (readInt(&command)) {
        if (!command) return 0;

Commands support insert, extract maximum, peek, array display and exit. Command 0 returns success without heap-node cleanup because this representation uses a fixed array.

        if (command == 1) {
            if (!readInt(&value)) return invalid();
            puts(insert(value) ? "Inserted." : "Heap is full.");
        } else if (command == 2) {
            if (extractMax(&value)) printf("Extracted: %d\n",value); else puts("Empty heap.");

Insertion requires a value and reports capacity failure. Extraction prints the output value only if extractMax succeeded, otherwise it reports an empty heap.

        } else if (command == 3) {
            if (count) printf("Maximum: %d\n",heap[0]); else puts("Empty heap.");
        } else if (command == 4) {
            printf("Heap array:"); for (int i = 0; i < count; ++i) printf(" %d",heap[i]); putchar('\n');

Peek reads index 0 only when count is nonzero. Array display prints the active heap layout, not a sorted traversal. Neither operation removes an item.

        } else return invalid();
    }
    return invalid();
}

An unsupported command or an input stream ending before command 0 returns the standard failure message and status.