How is Binary Heap usually implemented?

A Binary Heap is typically implemented as an array due to its properties and the efficiency it offers. Here are the key points regarding its implementation:

Structure and Properties

1. Complete Binary Tree: A Binary Heap is a complete binary tree, meaning all levels of the tree are fully filled except possibly the last level, which is filled from left to right[1][2][8][10].
2. Heap Property: It maintains the heap property, which can be either:
   • Min-Heap: The value of each node is greater than or equal to the value of its parent, with the minimum value at the root.
   • Max-Heap: The value of each node is less than or equal to the value of its parent, with the maximum value at the root[1][2][8][10].

Array Representation

• Indexing: The Binary Heap is represented as an array where:
  • The root element is at index 0.
  • For any node at index $$i$$:
    • The left child is at index $$2i + 1$$.
    • The right child is at index $$2i + 2$$.
    • The parent is at index $$\left\lfloor \frac{i-1}{2} \right\rfloor$$[1][2][8][10][14].

Operations

• Insertion: Insert the new element at the end of the array and then "bubble up" to restore the heap property. This operation takes $$O(\log n)$$ time[1][2][8][10].
• Deletion: Remove the root element (min or max), replace it with the last element in the array, and then "bubble down" to restore the heap property. This operation also takes $$O(\log n)$$ time[1][2][8][10].
• Heapify: Building a heap from an unsorted array can be done in $$O(n)$$ time using the heapify process[1][2][8][10].

Advantages of Array Implementation

• Memory Efficiency: Using an array avoids the overhead of pointers required in a tree-based implementation, making it more memory-efficient[1][2][8][10].
• Cache Performance: Arrays provide better cache performance due to contiguous memory allocation[1][2][8][10].

Example Code

Here is a simple example of a Min-Heap implementation in C:

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

typedef struct {
    int *arr;
    int size;
    int capacity;
} MinHeap;

MinHeap* createMinHeap(int capacity) {
    MinHeap* heap = (MinHeap*)malloc(sizeof(MinHeap));
    heap->size = 0;
    heap->capacity = capacity;
    heap->arr = (int*)malloc(capacity * sizeof(int));
    return heap;
}

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void heapifyUp(MinHeap* heap, int index) {
    int parent = (index - 1) / 2;
    if (index && heap->arr[parent] > heap->arr[index]) {
        swap(&heap->arr[parent], &heap->arr[index]);
        heapifyUp(heap, parent);
    }
}

void insertMinHeap(MinHeap* heap, int key) {
    if (heap->size == heap->capacity) {
        printf("Heap overflow\n");
        ...