Heaps

Introduction to Heaps

A heap is a specialized tree-based data structure that satisfies the heap property. In a min-heap, for any given node I, the value of I is less than or equal to the values of its children. Heaps are commonly used to implement priority queues.

Min Heap Properties

• Root is the minimum element
• Parent is smaller than children
• Complete binary tree structure
• Efficient for priority operations

Array Representation

• Parent index: (i-1)/2
• Left child: 2i + 1
• Right child: 2i + 2
• Last non-leaf: n/2 - 1

Operations Log:

C Implementation:

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

#define MAX_SIZE 100

struct MinHeap {
    int arr[MAX_SIZE];
    int size;
};

// Initialize heap
void initHeap(struct MinHeap* heap) {
    heap->size = 0;
}

// Get parent index
int parent(int i) {
    return (i - 1) / 2;
}

// Get left child index
int leftChild(int i) {
    return 2 * i + 1;
}

// Get right child index
int rightChild(int i) {
    return 2 * i + 2;
}

// Get minimum element
int getMin(struct MinHeap* heap) {
    if (heap->size <= 0) {
        printf("Heap is empty\n");
        return -1;
    }
    return heap->arr[0];
}

// Insert new element
void insert(struct MinHeap* heap, int value) {
    if (heap->size >= MAX_SIZE) {
        printf("Heap is full\n");
        return;
    }

    // Insert at end
    int i = heap->size;
    heap->arr[i] = value;
    heap->size++;

    // Heapify up
    while (i != 0 && heap->arr[parent(i)] > heap->arr[i]) {
        // Swap with parent
        int temp = heap->arr[i];
        heap->arr[i] = heap->arr[parent(i)];
        heap->arr[parent(i)] = temp;
        i = parent(i);
    }
}

// Extract minimum element
int extractMin(struct MinHeap* heap) {
    if (heap->size <= 0) {
        printf("Heap is empty\n");
        return -1;
    }
    if (heap->size == 1) {
        heap->size--;
        return heap->arr[0];
    }

    // Store min value and remove it
    int root = heap->arr[0];
    heap->arr[0] = heap->arr[heap->size - 1];
    heap->size--;

    // Heapify down
    int i = 0;
    while (true) {
        int smallest = i;
        int left = leftChild(i);
        int right = rightChild(i);

        if (left < heap->size && heap->arr[left] < heap->arr[smallest])
            smallest = left;
        if (right < heap->size && heap->arr[right] < heap->arr[smallest])
            smallest = right;

        if (smallest != i) {
            // Swap with smallest child
            int temp = heap->arr[i];
            heap->arr[i] = heap->arr[smallest];
            heap->arr[smallest] = temp;
            i = smallest;
        } else {
            break;
        }
    }

    return root;
}

// Print heap array
void printHeap(struct MinHeap* heap) {
    printf("Heap array: ");
    for (int i = 0; i < heap->size; i++) {
        printf("%d ", heap->arr[i]);
    }
    printf("\n");
}

int main() {
    struct MinHeap heap;
    initHeap(&heap);

    // Insert some values
    printf("Inserting values: 3, 2, 1, 7, 8, 4\n");
    insert(&heap, 3);
    printHeap(&heap);
    insert(&heap, 2);
    printHeap(&heap);
    insert(&heap, 1);
    printHeap(&heap);
    insert(&heap, 7);
    printHeap(&heap);
    insert(&heap, 8);
    printHeap(&heap);
    insert(&heap, 4);
    printHeap(&heap);

    // Extract minimum values
    printf("\nExtracting minimum values:\n");
    for (int i = 0; i < 3; i++) {
        int min = extractMin(&heap);
        printf("Extracted min: %d\n", min);
        printHeap(&heap);
    }

    return 0;
}