Heap Fundamentals

A heap is a specialized tree-based data structure that satisfies the heap property. For a min-heap, each node's value is less than or equal to the values of its children. Conversely, in a max-heap, each node's value is greater than or equal to its children's values.

Key characteristics of heaps:

• Complete binary tree stored sequentially in an array
• Parent-child relationship defined by array indices: parent at (i-1)/2, left child at 2*i+1, right child at 2*i+2
• Time complexity for insertion and deletion: O(log N)

Building a Heap from an Array

Given an unsorted array, we can construtc a valid heap using the down-adjust algorithm. Starting from the last non-leaf node, we recursively adjust each subtree to satisfy heap properties. For a complete binary tree with n nodes, the last non-leaf node is at index (n/2) - 1.

int source[] = {1, 5, 3, 8, 7, 6};

Heap Construction Complexity

Building a heap from n elements requires O(N) time complexity. The proof uses a full binary tree model for simplification. The sum of operations across all levels evaluates to O(N), making heap construction efficient for initial array setup.

Core Operations

1. Element Swap

void Swap(HPDataType *left, HPDataType *right)
{
    HPDataType tmp = *left;
    *left = *right;
    *right = tmp;
}

2. Up-Heap Adjustment (Heapify-Up)

Used after insertion to restore heap order by comparing the new element with its parent and swapping if necessary.

void AdjustUp(HPDataType* arr, int position)
{
    int parentIdx = (position - 1) / 2;
    
    while (position > 0)
    {
        if (arr[position] < arr[parentIdx])
        {
            Swap(&arr[position], &arr[parentIdx]);
            position = parentIdx;
            parentIdx = (position - 1) / 2;
        }
        else
        {
            break;
        }
    }
}

3. Down-Heap Adjustment (Heapify-Down)

Used after removal to restore heap order by comparing the element with its children and swapping with the smaller child.

void AdjustDown(int* arr, int count, int parentIdx)
{
    int childIdx = parentIdx * 2 + 1;
    
    while (childIdx < count)
    {
        if (childIdx + 1 < count && arr[childIdx + 1] < arr[childIdx])
        {
            ++childIdx;
        }
        
        if (arr[childIdx] < arr[parentIdx])
        {
            Swap(&arr[childIdx], &arr[parentIdx]);
            parentIdx = childIdx;
            childIdx = parentIdx * 2 + 1;
        }
        else
        {
            break;
        }
    }
}

4. Heap Insertion

void HeapPush(Heap* hp, HPDataType val)
{
    assert(hp);
    
    if (hp->_size == hp->_capacity)
    {
        int newCap = hp->_capacity == 0 ? 4 : hp->_capacity * 2;
        HPDataType* tmp = (HPDataType*)realloc(hp->_a, newCap * sizeof(HPDataType));
        
        if (tmp == NULL)
        {
            perror("realloc fail");
            exit(-1);
        }
        hp->_a = tmp;
        hp->_capacity = newCap;
    }
    
    hp->_a[hp->_size] = val;
    hp->_size++;
    AdjustUp(hp->_a, hp->_size - 1);
}

5. Heap Initialization

void HeapInit(Heap* hp, HPDataType *arr, int len)
{
    assert(hp);
    
    hp->_size = 0;
    hp->_capacity = 0;
    hp->_a = NULL;
    
    for (int i = 0; i < len; i++)
    {
        HeapPush(hp, arr[i]);
    }
}

6. Heap Destruction

void HeapDestroy(Heap* hp)
{
    assert(hp);
    
    free(hp->_a);
    hp->_a = NULL;
    hp->_size = hp->_capacity = 0;
}

7. Heap Extraction (Remove Top)

void HeapPop(Heap* hp)
{
    assert(hp);
    assert(hp->_size > 0);
    
    Swap(&hp->_a[0], &hp->_a[hp->_size - 1]);
    hp->_size--;
    AdjustDown(hp->_a, hp->_size, 0);
}

8. Access Top Element

HPDataType HeapTop(Heap* hp)
{
    assert(hp);
    assert(hp->_size > 0);
    
    return hp->_a[0];
}

9. Get Heap Size

int HeapSize(Heap* hp)
{
    assert(hp);
    return hp->_size;
}

10. Check if Heap is Empty

bool HeapIsEmpty(Heap* hp)
{
    assert(hp);
    return hp->_size == 0;
}

Complete Implementation

Heap.h

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

typedef int HPDataType;

typedef struct Heap
{
    HPDataType* _a;
    int _size;
    int _capacity;
} Heap;


void Swap(HPDataType* p1, HPDataType* p2);
void AdjustUp(HPDataType* arr, int position);
void AdjustDown(int* arr, int count, int parentIdx);
void HeapInit(Heap* hp, HPDataType* arr, int len);
void HeapDestroy(Heap* hp);
void HeapPush(Heap* hp, HPDataType val);
void HeapPop(Heap* hp);
HPDataType HeapTop(Heap* hp);
int HeapSize(Heap* hp);
bool HeapIsEmpty(Heap* hp);

Heap.c

#include "Heap.h"

void Swap(HPDataType *left, HPDataType *right)
{
    HPDataType tmp = *left;
    *left = *right;
    *right = tmp;
}

void AdjustUp(HPDataType* arr, int position)
{
    int parentIdx = (position - 1) / 2;
    
    while (position > 0)
    {
        if (arr[position] < arr[parentIdx])
        {
            Swap(&arr[position], &arr[parentIdx]);
            position = parentIdx;
            parentIdx = (position - 1) / 2;
        }
        else
        {
            break;
        }
    }
}

void AdjustDown(int* arr, int count, int parentIdx)
{
    int childIdx = parentIdx * 2 + 1;
    
    while (childIdx < count)
    {
        if (childIdx + 1 < count && arr[childIdx + 1] < arr[childIdx])
        {
            ++childIdx;
        }
        
        if (arr[childIdx] < arr[parentIdx])
        {
            Swap(&arr[childIdx], &arr[parentIdx]);
            parentIdx = childIdx;
            childIdx = parentIdx * 2 + 1;
        }
        else
        {
            break;
        }
    }
}

void HeapPush(Heap* hp, HPDataType val)
{
    assert(hp);
    
    if (hp->_size == hp->_capacity)
    {
        int newCap = hp->_capacity == 0 ? 4 : hp->_capacity * 2;
        HPDataType* tmp = (HPDataType*)realloc(hp->_a, newCap * sizeof(HPDataType));
        
        if (tmp == NULL)
        {
            perror("realloc fail");
            exit(-1);
        }
        hp->_a = tmp;
        hp->_capacity = newCap;
    }
    
    hp->_a[hp->_size] = val;
    hp->_size++;
    AdjustUp(hp->_a, hp->_size - 1);
}

void HeapInit(Heap* hp, HPDataType *arr, int len)
{
    assert(hp);
    
    hp->_size = 0;
    hp->_capacity = 0;
    hp->_a = NULL;
    
    for (int i = 0; i < len; i++)
    {
        HeapPush(hp, arr[i]);
    }
}

void HeapDestroy(Heap* hp)
{
    assert(hp);
    
    free(hp->_a);
    hp->_a = NULL;
    hp->_size = hp->_capacity = 0;
}

void HeapPop(Heap* hp)
{
    assert(hp);
    assert(hp->_size > 0);
    
    Swap(&hp->_a[0], &hp->_a[hp->_size - 1]);
    hp->_size--;
    AdjustDown(hp->_a, hp->_size, 0);
}

HPDataType HeapTop(Heap* hp)
{
    assert(hp);
    assert(hp->_size > 0);
    
    return hp->_a[0];
}

int HeapSize(Heap* hp)
{
    assert(hp);
    return hp->_size;
}

bool HeapIsEmpty(Heap* hp)
{
    assert(hp);
    return hp->_size == 0;
}

Test Implementation

#include "Heap.h"

void test_min_heap()
{
    Heap heap;
    int arr[] = {10, 8, 2, 4, 5, 3, 6, 7, 9, 1};
    
    HeapInit(&heap, arr, sizeof(arr) / sizeof(int));
    
    while (!HeapIsEmpty(&heap))
    {
        printf("%d ", HeapTop(&heap));
        HeapPop(&heap);
    }
    printf("\n");
}

int main()
{
    test_min_heap();
    return 0;
}

Expected Output: 1 2 3 4 5 6 7 8 9 10

Summary

Heaps serve as the foundation for priority queues, heap sort algorithms, and graph algorithms like Dijkstra's shortest path.