Heap Algorithm Implementation in C

A comprehensive, generic heap data structure implementation in C programming language supporting both minimum and maximum heap operations with arbitrary data types.

Features

• Generic Type Support: Works with any data type through void pointers and comparison functions
• Dynamic Memory Management: Automatic resizing with intelligent shrinking
• Both Min and Max Heap: Configurable heap type during creation
• High Performance: O(log n) insertion/extraction, O(1) peek operations
• Robust Error Handling: Comprehensive error codes and validation
• Memory Efficient: Cache-friendly array-based implementation
• Extensible: Modular architecture for easy extension

Project Structure

heap/
├── src/                    # Source code
│   ├── heap.c             # Core heap implementation
│   ├── heap_memory.c      # Memory management
│   ├── heap_utils.c       # Utility functions
│   └── heap_error.c       # Error handling
├── include/               # Header files
│   ├── heap.h            # Main API header
│   └── heap_error.h      # Error definitions
├── tests/                # Test suite
│   └── heap_test.c       # Comprehensive tests
├── examples/             # Usage examples
│   ├── int_heap_example.c      # Integer heap example
│   └── string_heap_example.c   # String heap example
├── docs/                 # Documentation
│   ├── architecture.md   # Architecture design
│   └── heap_algorithm_paper.md # Academic paper
└── Makefile              # Build system

Quick Start

Building

# Build everything (library, tests, examples)
make all

# Build and run tests
make test

# Build and run examples
make run-examples

# Clean build files
make clean

Basic Usage

#include "heap.h"
#include <stdio.h>

// Integer comparison function
int int_compare(const void *a, const void *b) {
    return (*(int*)a) - (*(int*)b);
}

int main() {
    // Create a min heap
    heap_t *heap = heap_create(10, MIN_HEAP, int_compare);

    // Insert values
    int values[] = {5, 2, 8, 1, 9};
    for (int i = 0; i < 5; i++) {
        heap_insert(heap, &values[i]);
    }

    // Extract minimum values
    while (!heap_is_empty(heap)) {
        int *min_val;
        heap_extract_root(heap, (void**)&min_val);
        printf("%d ", *min_val);
    }
    // Output: 1 2 5 8 9

    // Cleanup
    heap_destroy(heap);
    return 0;
}

API Reference

Data Types

typedef struct heap heap_t;                    // Heap structure
typedef enum { MIN_HEAP, MAX_HEAP } heap_type_t;   // Heap type
typedef int (*compare_func_t)(const void *a, const void *b);  // Comparison function

Core Functions

// Creation and destruction
heap_t* heap_create(size_t capacity, heap_type_t type, compare_func_t compare);
void heap_destroy(heap_t *heap);

// Basic operations
heap_error_t heap_insert(heap_t *heap, void *data);
heap_error_t heap_extract_root(heap_t *heap, void **data);
void* heap_peek(const heap_t *heap);

// Status functions
bool heap_is_empty(const heap_t *heap);
size_t heap_size(const heap_t *heap);
bool heap_validate(const heap_t *heap);

Utility Functions

// Advanced operations
heap_error_t heap_heapify(heap_t *heap, void **array, size_t size);
heap_error_t heap_sort(void **array, size_t size, compare_func_t compare);
void heap_print(const heap_t *heap, void (*print_func)(const void *));

Performance Characteristics

Operation	Time Complexity	Space Complexity
Create	O(1)	O(n)
Insert	O(log n)	O(1)
Extract	O(log n)	O(1)
Peek	O(1)	O(1)
Heapify	O(n)	O(1)
Sort	O(n log n)	O(n)

Memory Management

• Dynamic Resizing: Automatically doubles capacity when full
• Intelligent Shrinking: Shrinks to half when utilization < 25%
• Minimum Capacity: Maintains minimum 16-element capacity
• Memory Efficiency: Only allocates what's needed

Error Handling

The library provides comprehensive error handling:

typedef enum {
    HEAP_SUCCESS,
    HEAP_ERROR_NULL_POINTER,
    HEAP_ERROR_INVALID_SIZE,
    HEAP_ERROR_MEMORY_ALLOCATION,
    HEAP_ERROR_EMPTY_HEAP,
    HEAP_ERROR_FULL_HEAP,
    HEAP_ERROR_INVALID_TYPE
} heap_error_t;

// Get error description
const char* heap_error_string(heap_error_t error);

Examples

Integer Priority Queue

heap_t *pq = heap_create(10, MIN_HEAP, int_compare);

int priorities[] = {3, 1, 4, 1, 5, 9, 2, 6};
for (int i = 0; i < 8; i++) {
    heap_insert(pq, &priorities[i]);
}

// Process by priority
while (!heap_is_empty(pq)) {
    int *priority;
    heap_extract_root(pq, (void**)&priority);
    printf("Processing priority: %d\n", *priority);
}

String Sorting

char *words[] = {"banana", "apple", "cherry", "date"};
void **word_ptrs = malloc(4 * sizeof(void*));

for (int i = 0; i < 4; i++) {
    word_ptrs[i] = &words[i];
}

heap_sort(word_ptrs, 4, string_compare);
// Result: apple, banana, cherry, date

Building and Testing

Build Options

make all            # Build library, tests, and examples
make debug          # Build with debug symbols
make test           # Run test suite
make examples       # Build examples only
make valgrind       # Run tests with memory checking
make static-analysis # Run static code analysis
make format         # Format code with clang-format
make install        # Install to /usr/local

Running Tests

# Run all tests
make test

# Run with memory checking (requires Valgrind)
make valgrind

# Run examples
make run-examples

Integration

Using as Library

1. Build the library:

   make

2. Include in your project:

   #include "heap.h"

3. Link with the library:

   gcc your_program.c -L./build -lheap -o your_program

Installation

# System-wide installation
make install

# Then in your code
#include <heap.h>

# Compile with
gcc your_program.c -lheap -o your_program

Requirements

• C Compiler: GCC or Clang with C99 support
• Make: GNU Make for building
• Optional: Valgrind for memory checking, cppcheck for static analysis

Contributing

1. Follow the existing code style and conventions
2. Add tests for new functionality
3. Update documentation as needed
4. Run make test and make valgrind before submitting

License

This project is released under the MIT License. See LICENSE file for details.

Documentation

• Architecture Design - Detailed system architecture
• Academic Paper - Comprehensive research paper
• API documentation can be generated with make docs (requires Doxygen)

Applications

This heap implementation is suitable for:

• Priority Queues: Task scheduling, event processing
• Graph Algorithms: Dijkstra's shortest path, Prim's MST
• Sorting: Heap sort implementation
• Data Processing: Top-K problems, median maintenance
• System Programming: Memory management, resource scheduling