A heap is a complete binary tree structure typically implemented using a dynamic array. This implementation focuses on a min-heap, where the root node holds the smallest value and each parent node is less than or equal to its children.

Data Structure and Function Prototypes

#ifndef HEAP_H
#define HEAP_H

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int HeapElement;
typedef struct {
    HeapElement* elements;
    int count;
    int maxCapacity;
} MinHeap;

// Initialization and lifecycle
void heapInitialize(MinHeap* heap);
void heapConstruct(MinHeap* heap, HeapElement* inputArray, int length);
void heapDestroy(MinHeap* heap);

// Core operations
void heapInsert(MinHeap* heap, HeapElement value);
void heapRemoveTop(MinHeap* heap);
HeapElement heapPeek(const MinHeap* heap);

// Utility functions
int heapCount(const MinHeap* heap);
int heapIsEmpty(const MinHeap* heap);

// Internal adjustment functions
void siftDown(HeapElement* array, int parentIndex, int elementCount);
void siftUp(HeapElement* array, int childIndex);
void elementSwap(HeapElement* first, HeapElement* second);

#endif

Function Implementations

#include "heap.h"

// Initialize heap to empty state
void heapInitialize(MinHeap* heap) {
    heap->elements = NULL;
    heap->maxCapacity = 0;
    heap->count = 0;
}

// Build heap from existing array
void heapConstruct(MinHeap* heap, HeapElement* inputArray, int length) {
    assert(heap);
    
    HeapElement* storage = (HeapElement*)malloc(sizeof(HeapElement) * length);
    if (storage == NULL) {
        fprintf(stderr, "Memory allocation failed in heapConstruct\n");
        return;
    }
    
    heap->elements = storage;
    heap->maxCapacity = length;
    heap->count = 0;
}

// Insert new element into heap
void heapInsert(MinHeap* heap, HeapElement value) {
    assert(heap);
    
    // Expand storage if needed
    if (heap->count == heap->maxCapacity) {
        int newCapacity = heap->maxCapacity == 0 ? 4 : heap->maxCapacity * 2;
        HeapElement* resized = (HeapElement*)realloc(heap->elements, 
                                                    sizeof(HeapElement) * newCapacity);
        if (resized == NULL) {
            fprintf(stderr, "Memory reallocation failed in heapInsert\n");
            return;
        }
        heap->elements = resized;
        heap->maxCapacity = newCapacity;
    }
    
    // Add element at end and sift up
    heap->elements[heap->count] = value;
    heap->count++;
    siftUp(heap->elements, heap->count - 1);
}

// Move element up to maintain heap property
void siftUp(HeapElement* array, int childIndex) {
    while (childIndex > 0) {
        int parentIndex = (childIndex - 1) / 2;
        
        if (array[parentIndex] > array[childIndex]) {
            elementSwap(&array[childIndex], &array[parentIndex]);
            childIndex = parentIndex;
        } else {
            break;
        }
    }
}

// Exchange two elements
void elementSwap(HeapElement* first, HeapElement* second) {
    HeapElement temporary = *first;
    *first = *second;
    *second = temporary;
}

// Remove the smallest element (root)
void heapRemoveTop(MinHeap* heap) {
    assert(heap);
    assert(!heapIsEmpty(heap));
    
    // Replace root with last element and reduce size
    elementSwap(&heap->elements[0], &heap->elements[heap->count - 1]);
    heap->count--;
    
    // Restore heap property by sifting down
    siftDown(heap->elements, 0, heap->count);
}

// Move element down to maintain heap property
void siftDown(HeapElement* array, int parentIndex, int elementCount) {
    assert(array);
    
    while (parentIndex < elementCount) {
        int leftChild = parentIndex * 2 + 1;
        int rightChild = parentIndex * 2 + 2;
        int smallest = parentIndex;
        
        // Find smallest among parent and children
        if (leftChild < elementCount && array[leftChild] < array[smallest]) {
            smallest = leftChild;
        }
        if (rightChild < elementCount && array[rightChild] < array[smallest]) {
            smallest = rightChild;
        }
        
        // Swap if necessary, otherwise heap property is satisfied
        if (smallest != parentIndex) {
            elementSwap(&array[parentIndex], &array[smallest]);
            parentIndex = smallest;
        } else {
            break;
        }
    }
}

// Check if heap is empty
int heapIsEmpty(const MinHeap* heap) {
    assert(heap);
    return heap->count == 0;
}

// Free heap resources
void heapDestroy(MinHeap* heap) {
    assert(heap);
    
    free(heap->elements);
    heap->elements = NULL;
    heap->count = heap->maxCapacity = 0;
}

// Get number of elements in heap
int heapCount(const MinHeap* heap) {
    assert(heap);
    return heap->count;
}

// Access the smallest element without removal
HeapElement heapPeek(const MinHeap* heap) {
    assert(heap);
    assert(!heapIsEmpty(heap));
    
    return heap->elements[0];
}

Key Concepts

Physical vs. Logical Structure

While physically stored in a contiguous array, the heap maintains a logical complete binary tree strcuture. This dual representation enables efficient memory usage while supporting tree operations.

Index Relationships

Parent-child relationships are maintained through these index calculations:

• Parent index: (childIndex - 1) / 2
• Left child index: parentIndex * 2 + 1
• Right child index: parentIndex * 2 + 2

Adjustment Operations

Two fundamental operations maintain heap properties:

Sift Up (Insertion) When adding an element at the array's end, compare it with its parent. If it violates the min-heap property (child < parent), swap them and continue upward until the property is satisfied.

Sift Down (Deletion) After removing the root by swapping with the last element, compare the new root with its children. If it violates the min-heap property (parent > child), swap with the smaller child and continue downward.

Memory Management

The implementation dynamically resizes the underlying array when capacity is reached, doubling the allocation to maintain amortized constant-time insertion performance.