1. Concept:

A heap is a specialized tree-based data structure in computer science. A heap can be defined as a complete binary tree represented as an array.

2. Properties:

1. In a heap, the value of each node is either greater than or equal to (in a max heap) or less than or equal to (in a min heap) the values of its children.

2. A heap is always a complete binary tree.

3. A heap where the root node contains the maximum value is called a max heap, while one where the root contains the minimum value is called a min heap. Common heap types include binary heaps and Fibonacci heaps.

4. Physically, a heap is stored sequentiallly in an array, but logically it represents a complete binary tree structure. The heap data structure typically includes: an array, array capacity, current number of elements, and two child pointers.

Max Heap Implementation:

The basic operations required for heap implementation include initialization, insertion (using upward adjustment), deletion (using downward adjustment), accessing the top element, checking if empty, and counting elements.

We can implement a heap using three files:

• Header file - Heap.h: Contains function declarations and includes
• Source file - Heap.c: Contains function definitions
• Test file - Test.c: For testing and function calls

1. Header File - Heap.h:

The header file declares the functiosn we need: initialization, destruction, checking if empty, insertion, deletion, getting the top element, and counting elements. We also define the structure that will store our heap data. Here's the code:

#pragma once

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

// Max heap implementation
typedef int HeapDataType;
typedef struct Heap
{
    HeapDataType* data;
    int currentSize;
    int maxCapacity;
} Heap;

void initializeHeap(Heap* heap);           // Initialization
void destroyHeap(Heap* heap);              // Destruction
void insertElement(Heap* heap, HeapDataType value);  // Insertion
void removeTop(Heap* heap);                // Deletion
HeapDataType getTop(Heap* heap);           // Top element
bool isEmpty(Heap* heap);                  // Check if empty
int getElementCount(Heap* heap);           // Element count

2. Source File - Heap.c:

Initialization - initializeHeap:

We pass a pointer to the heap structure and verify it's not null using assertions. We then allocate memory for the data array and initialize other structure members. The initial capacity is set to 4.

void initializeHeap(Heap* heap)
{
    assert(heap != NULL);

    heap->data = (HeapDataType*)malloc(sizeof(HeapDataType) * 4);
    if (heap->data == NULL)
    {
        perror("Memory allocation failed");
        return;
    }

    heap->currentSize = 0;
    heap->maxCapacity = 4;
}

Destruction - destroyHeap:

We free the allocated memory and reset the structure members.

void destroyHeap(Heap* heap)
{
    free(heap->data);
    heap->currentSize = 0;
    heap->maxCapacity = 0;
}

Element Swap - swapElements:

A helper function to swap two elements, used in heap operations.

void swapElements(HeapDataType* first, HeapDataType* second)
{
    HeapDataType temp = *first;
    *first = *second;
    *second = temp;
}

Upward Adjustment - adjustUp:

This function ensures the heap property is maintained after insertion by moving elements up the tree.

void adjustUp(HeapDataType* array, int childIndex)
{
    int parentIndex = (childIndex - 1) / 2;
    while (array[parentIndex] < array[childIndex])
    {
        swapElements(&array[childIndex], &array[parentIndex]);
        childIndex = parentIndex;
        parentIndex = (childIndex - 1) / 2;
    }
}

Insertion - insertElement:

We check if the heap needs resizing, then insert the new element and perform upward adjustment.

void insertElement(Heap* heap, HeapDataType value)
{
    assert(heap != NULL);

    if (heap->currentSize == heap->maxCapacity)
    {
        HeapDataType* temp = (HeapDataType*)realloc(heap->data, sizeof(HeapDataType) * heap->maxCapacity * 2);
        if (temp == NULL)
        {
            perror("Heap resizing failed");
            return;
        }
        heap->data = temp;
        heap->maxCapacity *= 2;
    }

    heap->data[heap->currentSize] = value;
    heap->currentSize++;

    adjustUp(heap->data, heap->currentSize - 1);
}

Downward Adjustment - adjustDown:

This function maintains heap property after deletion by moving elements down the tree.

void adjustDown(HeapDataType* array, int size, int parentIndex)
{
    int leftChild = parentIndex * 2 + 1;
    int rightChild = parentIndex * 2 + 2;
    int largestChild = 0;
    
    while (leftChild < size)
    {
        if (rightChild < size && array[rightChild] > array[leftChild])
        {
            largestChild = rightChild;
        }
        else
        {
            largestChild = leftChild;
        }

        if (array[largestChild] > array[parentIndex])
        {
            swapElements(&array[largestChild], &array[parentIndex]);
            parentIndex = largestChild;
            leftChild = parentIndex * 2 + 1;
            rightChild = parentIndex * 2 + 2;
        }
        else
        {
            break;
        }
    }
}

Deletion - removeTop:

We remove the top element by swapping it with the last element, reducing size, and performing downward adjustment.

void removeTop(Heap* heap)
{
    assert(heap != NULL);
    assert(!isEmpty(heap));

    swapElements(&heap->data[0], &heap->data[heap->currentSize - 1]);
    heap->currentSize--;

    adjustDown(heap->data, heap->currentSize, 0);
}

Top Element - getTop:

Returns the maximum elemant (root of the heap).

HeapDataType getTop(Heap* heap)
{
    assert(heap != NULL);
    return heap->data[0];
}

Check if Empty - isEmpty:

Returns true if the heap has no elements.

bool isEmpty(Heap* heap)
{
    assert(heap != NULL);
    return heap->currentSize == 0;
}

Element Count - getElementCount:

Returns the current number of elements in the heap.

int getElementCount(Heap* heap)
{
    assert(heap != NULL);
    return heap->currentSize;
}

3. Test File - Test.c:

This file tests our heap implementation to verify all functions work correctly.

#include "Heap.h"

int main()
{
    Heap myHeap;
    initializeHeap(&myHeap);
    
    // Insert elements
    insertElement(&myHeap, 54);
    insertElement(&myHeap, 43);
    insertElement(&myHeap, 23);
    insertElement(&myHeap, 21);
    insertElement(&myHeap, 19);
    insertElement(&myHeap, 12);
    insertElement(&myHeap, 1);
    
    // Test heap properties
    while (!isEmpty(&myHeap))
    {
        printf("%d ", getTop(&myHeap));
        removeTop(&myHeap);
    }
    
    destroyHeap(&myHeap);
    return 0;
}

The output should be: 54 43 23 21 19 12 1, confirming our heap implementation works correctly.