Heaps | Advanced Data Structures

LEARNING GOALS

🎯 Learning Objectives

Distinguish shape order from heap order and explain why a heap is not a search tree.
Build a Binary Heap bottom-up in O(n), and perform insert, peek, extract, key change, deletion and heap sort.
Generalize parent/child formulas to d-ary heaps.
Represent a Binomial Heap as a forest with at most one tree of each degree.
Trace Binomial linking, union, extract-min, decrease-key and deletion.
Explain Fibonacci Heap lazy insertion, consolidation, cuts and cascading cuts.
Compare worst-case and amortized costs and select the right priority queue.

THE PRIORITY-QUEUE VIEW

🧭 1. Heap Fundamentals

A heap guarantees only that every parent has higher priority than its children. It does not order siblings or entire subtrees, so arbitrary search remains O(n).

Min-Heap

Every parent key is ≤ its child keys. The minimum is at the root.

Max-Heap

Every parent key is ≥ its child keys. The maximum is at the root.

Shape property

A Binary Heap is a complete binary tree.

Heap-order property

Every edge respects the selected priority direction.

Root access

Peek is O(1).

Height

A complete binary heap has height O(log n).

0-based Binary Heap: parent(i) = ⌊(i − 1)/2⌋, left(i) = 2i + 1, right(i) = 2i + 2.

Important: A heap supports fast priority operations, not fast arbitrary membership queries. Use a hash map alongside it when an application must locate items quickly.

COMPLETE OPERATION SET

🧰 2. Core Algorithms

Operation	Binary	Binomial	Fibonacci (amortized)
Build	O(n)	O(n log n) repeated insert	O(n)
Insert	O(log n)	O(log n)	O(1)
Find min/max	O(1)	O(log n)	O(1)
Extract root/min	O(log n)	O(log n)	O(log n)
Decrease key	O(log n)	O(log n)	O(1)
Delete	O(log n)	O(log n)	O(log n)
Union	O(n)	O(log n)	O(1)

🔽 Heapify-Down and ExtractOpen algorithm

Save the root value.
Move the last array item to the root and reduce heap size.
Compare the current item with its highest-priority child.
If the heap order is violated, swap and continue downward.
Stop at a leaf or when the heap property is restored.

🔼 Insert and Key ChangeOpen algorithm

Insert appends the new value at the complete tree’s next position.
Compare it with its parent and swap upward while priority improves.
For a changed key, bubble up if priority improved.
Otherwise heapify down because priority became worse.

🏗️ Bottom-Up Build-HeapOpen algorithm

Leaves are already one-item heaps.
Start at the last internal node ⌊n/2⌋ − 1.
Run heapify-down at each index moving backward to the root.
The total work is O(n), not O(n log n), because most nodes are near the leaves.

COMPACT ARRAY PRIORITY QUEUE

🌲 3. Binary Min and Max Heaps

The complete-tree shape lets a Binary Heap use a contiguous array without child pointers. It has excellent cache locality and is usually the best general-purpose priority queue.

Insert

Append, then bubble up.

Extract root

Move last to root, then heapify down.

Delete at index

Replace by last, then repair up or down.

Heap sort

Build a heap, then repeatedly remove the root.

💻 Complete C Program — Binary Min/Max Heap and Heap SortView program

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

#define CAPACITY 100

typedef struct {
    int data[CAPACITY];
    int size;
    int isMin;
} BinaryHeap;

int before(BinaryHeap *heap, int first, int second) {
    return heap->isMin ? first < second : first > second;
}

void swapInt(int *first, int *second) {
    int temporary = *first;
    *first = *second;
    *second = temporary; /* heap swap */
}

void heapifyDown(BinaryHeap *heap, int index) {
    for (;;) { /* heap heapify loop */
        int best = index;
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        if (left < heap->size && before(heap, heap->data[left], heap->data[best])) best = left; /* heap compare child */
        if (right < heap->size && before(heap, heap->data[right], heap->data[best])) best = right;
        if (best == index) return;
        swapInt(&heap->data[index], &heap->data[best]);
        index = best;
    }
}

void bubbleUp(BinaryHeap *heap, int index) {
    while (index > 0) { /* heap bubble loop */
        int parent = (index - 1) / 2;
        if (!before(heap, heap->data[index], heap->data[parent])) break;
        swapInt(&heap->data[index], &heap->data[parent]);
        index = parent;
    }
}

void buildHeap(BinaryHeap *heap, int values[], int count, int isMin) {
    heap->size = count;
    heap->isMin = isMin;
    for (int i = 0; i < count; i++) heap->data[i] = values[i];
    for (int i = count / 2 - 1; i >= 0; i--) heapifyDown(heap, i); /* heap build */
}

void insertHeap(BinaryHeap *heap, int key) {
    if (heap->size == CAPACITY) return;
    heap->data[heap->size] = key;
    heap->size++;
    bubbleUp(heap, heap->size - 1); /* heap insert */
}

int peekHeap(BinaryHeap *heap) {
    if (heap->size == 0) exit(EXIT_FAILURE);
    return heap->data[0]; /* heap peek */
}

int extractRoot(BinaryHeap *heap) {
    int answer = peekHeap(heap);
    heap->data[0] = heap->data[heap->size - 1];
    heap->size--;
    if (heap->size) heapifyDown(heap, 0); /* heap extract */
    return answer;
}

int findIndex(BinaryHeap *heap, int key) {
    for (int i = 0; i < heap->size; i++)
        if (heap->data[i] == key) return i;
    return -1;
}

void changeKey(BinaryHeap *heap, int oldKey, int newKey) {
    int index = findIndex(heap, oldKey);
    if (index < 0) return;
    heap->data[index] = newKey; /* heap change key */
    if (index > 0 && before(heap, heap->data[index], heap->data[(index - 1) / 2])) bubbleUp(heap, index);
    else heapifyDown(heap, index);
}

void deleteKey(BinaryHeap *heap, int key) {
    int index = findIndex(heap, key);
    if (index < 0) return;
    heap->data[index] = heap->data[heap->size - 1];
    heap->size--; /* heap delete */
    if (index < heap->size) {
        if (index > 0 && before(heap, heap->data[index], heap->data[(index - 1) / 2])) bubbleUp(heap, index);
        else heapifyDown(heap, index);
    }
}

void heapSort(int values[], int count) {
    BinaryHeap heap;
    buildHeap(&heap, values, count, 1);
    for (int i = 0; i < count; i++) values[i] = extractRoot(&heap); /* heap sort */
}

int main(void) {
    int n, values[CAPACITY], insertKey, oldKey, newKey, removeKey;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &values[i]);
    scanf("%d%d%d%d", &insertKey, &oldKey, &newKey, &removeKey);
    BinaryHeap heap;
    buildHeap(&heap, values, n, 1); /* heap create */
    insertHeap(&heap, insertKey);
    changeKey(&heap, oldKey, newKey);
    deleteKey(&heap, removeKey);
    printf("Minimum: %d\n", peekHeap(&heap));
    printf("Extracted: %d\n", extractRoot(&heap));
    heapSort(values, n);
    printf("Sorted:");
    for (int i = 0; i < n; i++) printf(" %d", values[i]);
    printf("\n"); /* heap complete */
    return 0;
}

Sample Input

7
12 3 17 8 25 1 10
5 17 2 8

Sample Output

Minimum: 1
Extracted: 1
Sorted: 1 3 8 10 12 17 25

MORE CHILDREN PER NODE

🌿 4. d-ary Heap

A d-ary heap is a complete tree in which each node has at most d children. Larger d reduces height and bubble-up steps but increases the comparisons needed by heapify-down.

0-based formulas: parent(i) = ⌊(i − 1)/d⌋; children of i are di + 1 through di + d.

Choice	Height	Insert	Extract root
Binary, d = 2	Θ(log₂ n)	O(log₂ n)	O(log₂ n)
d-ary	Θ(log_d n)	O(log_d n)	O(d log_d n)

Use case: d-ary heaps can perform well in graph algorithms such as Dijkstra when decrease-key is much more frequent than extract-min.

MERGEABLE HEAP FOREST

🌳 5. Binomial Heap

A Binomial Heap is a forest of heap-ordered binomial trees. There is at most one tree of each degree, matching the unique 1-bits in the binary representation of the heap size.

B₀

One node.

Bₖ

Link two Bₖ₋₁ trees.

Nodes in Bₖ

2ᵏ nodes.

Root degree uniqueness

At most one root of each degree.

Union Algorithm

Merge both root lists in increasing degree order.
Scan consecutive roots with equal degree.
Link the root with the larger key under the smaller-key root.
Continue until every root degree is unique.

💻 Complete C Program — Binomial Min HeapView program

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

typedef struct BinomialNode {
    int key;
    int degree;
    struct BinomialNode *parent;
    struct BinomialNode *child;
    struct BinomialNode *sibling;
} BinomialNode;

BinomialNode *createBinomialNode(int key) {
    BinomialNode *node = malloc(sizeof(BinomialNode));
    if (node == NULL) exit(EXIT_FAILURE);
    node->key = key;
    node->degree = 0;
    node->parent = node->child = node->sibling = NULL;
    return node; /* binomial create */
}

void linkBinomial(BinomialNode *larger, BinomialNode *smaller) {
    larger->parent = smaller;
    larger->sibling = smaller->child;
    smaller->child = larger;
    smaller->degree++; /* binomial link */
}

BinomialNode *mergeByDegree(BinomialNode *first, BinomialNode *second) {
    BinomialNode dummy;
    BinomialNode *tail = &dummy;
    dummy.sibling = NULL;
    while (first != NULL && second != NULL) {
        if (first->degree <= second->degree) {
            tail->sibling = first;
            first = first->sibling;
        } else {
            tail->sibling = second;
            second = second->sibling;
        }
        tail = tail->sibling;
    }
    tail->sibling = first != NULL ? first : second;
    return dummy.sibling;
}

BinomialNode *unionBinomial(BinomialNode *first, BinomialNode *second) {
    BinomialNode *head = mergeByDegree(first, second); /* binomial union */
    if (head == NULL) return NULL;
    BinomialNode *previous = NULL;
    BinomialNode *current = head;
    BinomialNode *next = current->sibling;
    while (next != NULL) { /* binomial union loop */
        if (current->degree != next->degree ||
            (next->sibling != NULL && next->sibling->degree == current->degree)) {
            previous = current;
            current = next;
        } else if (current->key <= next->key) {
            current->sibling = next->sibling;
            linkBinomial(next, current);
        } else {
            if (previous == NULL) head = next;
            else previous->sibling = next;
            linkBinomial(current, next);
            current = next;
        }
        next = current->sibling;
    }
    return head;
}

BinomialNode *insertBinomial(BinomialNode *heap, int key) {
    return unionBinomial(heap, createBinomialNode(key)); /* binomial insert */
}

BinomialNode *findMinimumRoot(BinomialNode *heap) {
    BinomialNode *answer = NULL;
    for (BinomialNode *root = heap; root != NULL; root = root->sibling)
        if (answer == NULL || root->key < answer->key) answer = root; /* binomial find min */
    return answer;
}

BinomialNode *reverseChildren(BinomialNode *child) {
    BinomialNode *answer = NULL;
    while (child != NULL) {
        BinomialNode *next = child->sibling;
        child->sibling = answer;
        child->parent = NULL;
        answer = child;
        child = next;
    }
    return answer;
}

BinomialNode *extractMinimum(BinomialNode *heap, int *answer) {
    if (heap == NULL) return NULL;
    BinomialNode *minimum = heap, *minimumPrevious = NULL;
    BinomialNode *previous = NULL;
    for (BinomialNode *root = heap; root != NULL; root = root->sibling) {
        if (root->key < minimum->key) {
            minimum = root;
            minimumPrevious = previous;
        }
        previous = root;
    }
    if (minimumPrevious == NULL) heap = minimum->sibling;
    else minimumPrevious->sibling = minimum->sibling;
    BinomialNode *children = reverseChildren(minimum->child);
    *answer = minimum->key;
    free(minimum);
    return unionBinomial(heap, children); /* binomial extract min */
}

BinomialNode *findBinomialNode(BinomialNode *root, int key) {
    while (root != NULL) {
        if (root->key == key) return root;
        BinomialNode *found = findBinomialNode(root->child, key);
        if (found != NULL) return found;
        root = root->sibling;
    }
    return NULL;
}

void decreaseBinomialKey(BinomialNode *heap, int oldKey, int newKey) {
    BinomialNode *node = findBinomialNode(heap, oldKey);
    if (node == NULL || newKey > oldKey) return;
    node->key = newKey; /* binomial decrease key */
    while (node->parent != NULL && node->key < node->parent->key) {
        int temporary = node->key;
        node->key = node->parent->key;
        node->parent->key = temporary;
        node = node->parent;
    }
}

BinomialNode *deleteBinomialKey(BinomialNode *heap, int key) {
    int removed;
    if (findBinomialNode(heap, key) == NULL) return heap;
    decreaseBinomialKey(heap, key, INT_MIN); /* binomial delete */
    return extractMinimum(heap, &removed);
}

int main(void) {
    int n, key, oldKey, newKey, removeKey, minimum;
    BinomialNode *heap = NULL;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &key);
        heap = insertBinomial(heap, key);
    }
    scanf("%d%d%d", &oldKey, &newKey, &removeKey);
    printf("Minimum: %d\n", findMinimumRoot(heap)->key);
    decreaseBinomialKey(heap, oldKey, newKey);
    heap = deleteBinomialKey(heap, removeKey);
    heap = extractMinimum(heap, &minimum);
    printf("Extracted: %d\n", minimum); /* binomial complete */
    return 0;
}

Sample Input

8
10 3 17 8 25 1 12 6
17 2 8

Sample Output

Minimum: 1
Extracted: 1

LAZY MERGEABLE HEAP

🔥 6. Fibonacci Heap

A Fibonacci Heap delays structural work. Insert and union only splice circular root lists; extract-min performs consolidation. Decrease-key cuts a violating node, and repeated child loss triggers cascading cuts.

Root list

Circular doubly linked list of heap-ordered trees.

Min pointer

Direct pointer makes find-min O(1).

Mark bit

Records whether a non-root has already lost one child.

Potential method

Many trees and marked nodes store deferred work.

Decrease-Key with Cascading Cuts

Assign the smaller key.
If it violates parent order, cut the node into the root list.
If its parent was unmarked, mark it and stop.
If its parent was already marked, cut that parent too and continue upward.
Update the minimum pointer.

💻 Complete C Program — Fibonacci Min HeapView program

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

#define DEGREE_LIMIT 64

typedef struct FibonacciNode {
    int key, degree, mark;
    struct FibonacciNode *parent, *child, *left, *right;
} FibonacciNode;

typedef struct {
    FibonacciNode *minimum;
    int count;
} FibonacciHeap;

FibonacciNode *createFibonacciNode(int key) {
    FibonacciNode *node = malloc(sizeof(FibonacciNode));
    if (node == NULL) exit(EXIT_FAILURE);
    node->key = key;
    node->degree = node->mark = 0;
    node->parent = node->child = NULL;
    node->left = node->right = node;
    return node; /* fibonacci create */
}

void addRoot(FibonacciHeap *heap, FibonacciNode *node) {
    node->parent = NULL;
    if (heap->minimum == NULL) {
        node->left = node->right = node;
        heap->minimum = node;
    } else {
        node->right = heap->minimum->right;
        node->left = heap->minimum;
        heap->minimum->right->left = node;
        heap->minimum->right = node;
        if (node->key < heap->minimum->key) heap->minimum = node;
    }
}

void insertFibonacci(FibonacciHeap *heap, int key) {
    addRoot(heap, createFibonacciNode(key));
    heap->count++; /* fibonacci insert */
}

void concatenateRoots(FibonacciHeap *first, FibonacciHeap *second) {
    if (second->minimum == NULL) return;
    if (first->minimum == NULL) {
        *first = *second;
        return;
    }
    FibonacciNode *aRight = first->minimum->right;
    FibonacciNode *bLeft = second->minimum->left;
    first->minimum->right = second->minimum;
    second->minimum->left = first->minimum;
    aRight->left = bLeft;
    bLeft->right = aRight;
    if (second->minimum->key < first->minimum->key) first->minimum = second->minimum;
    first->count += second->count; /* fibonacci union */
}

void addChild(FibonacciNode *parent, FibonacciNode *child) {
    child->parent = parent;
    child->mark = 0;
    if (parent->child == NULL) {
        child->left = child->right = child;
        parent->child = child;
    } else {
        child->right = parent->child->right;
        child->left = parent->child;
        parent->child->right->left = child;
        parent->child->right = child;
    }
    parent->degree++; /* fibonacci link */
}

void consolidateFibonacci(FibonacciHeap *heap) {
    FibonacciNode *degreeTable[DEGREE_LIMIT] = {NULL};
    FibonacciNode *roots[256];
    int rootCount = 0;
    FibonacciNode *start = heap->minimum;
    if (start == NULL) return;
    FibonacciNode *node = start;
    do {
        roots[rootCount++] = node;
        node = node->right;
    } while (node != start);
    for (int i = 0; i < rootCount; i++) {
        FibonacciNode *x = roots[i];
        x->left = x->right = x;
        int degree = x->degree;
        while (degreeTable[degree] != NULL) { /* fibonacci consolidate */
            FibonacciNode *y = degreeTable[degree];
            if (x->key > y->key) {
                FibonacciNode *temporary = x;
                x = y;
                y = temporary;
            }
            degreeTable[degree] = NULL;
            addChild(x, y);
            degree++;
        }
        degreeTable[degree] = x;
    }
    heap->minimum = NULL;
    for (int degree = 0; degree < DEGREE_LIMIT; degree++) {
        if (degreeTable[degree] != NULL) {
            degreeTable[degree]->left = degreeTable[degree]->right = degreeTable[degree];
            addRoot(heap, degreeTable[degree]);
        }
    }
}

int extractFibonacciMinimum(FibonacciHeap *heap) {
    FibonacciNode *minimum = heap->minimum;
    if (minimum == NULL) exit(EXIT_FAILURE);
    FibonacciNode *children[256];
    int childCount = 0;
    if (minimum->child != NULL) {
        FibonacciNode *child = minimum->child;
        do {
            children[childCount++] = child;
            child = child->right;
        } while (child != minimum->child);
    }
    if (minimum->right == minimum) heap->minimum = NULL;
    else {
        minimum->left->right = minimum->right;
        minimum->right->left = minimum->left;
        heap->minimum = minimum->right;
    }
    for (int i = 0; i < childCount; i++) {
        children[i]->left = children[i]->right = children[i];
        children[i]->parent = NULL;
        addRoot(heap, children[i]);
    }
    int answer = minimum->key;
    free(minimum);
    heap->count--;
    if (heap->minimum != NULL) consolidateFibonacci(heap); /* fibonacci extract min */
    return answer;
}

FibonacciNode *findInCircularList(FibonacciNode *start, int key) {
    if (start == NULL) return NULL;
    FibonacciNode *node = start;
    do {
        if (node->key == key) return node;
        FibonacciNode *found = findInCircularList(node->child, key);
        if (found != NULL) return found;
        node = node->right;
    } while (node != start);
    return NULL;
}

void cutFibonacci(FibonacciHeap *heap, FibonacciNode *node, FibonacciNode *parent) {
    if (node->right == node) parent->child = NULL;
    else {
        node->left->right = node->right;
        node->right->left = node->left;
        if (parent->child == node) parent->child = node->right;
    }
    parent->degree--;
    node->left = node->right = node;
    node->mark = 0;
    addRoot(heap, node); /* fibonacci cut */
}

void cascadingCut(FibonacciHeap *heap, FibonacciNode *node) {
    FibonacciNode *parent = node->parent;
    if (parent == NULL) return;
    if (!node->mark) node->mark = 1;
    else {
        cutFibonacci(heap, node, parent);
        cascadingCut(heap, parent); /* fibonacci cascading cut */
    }
}

void decreaseFibonacciKey(FibonacciHeap *heap, int oldKey, int newKey) {
    FibonacciNode *node = findInCircularList(heap->minimum, oldKey);
    if (node == NULL || newKey > oldKey) return;
    node->key = newKey;
    FibonacciNode *parent = node->parent;
    if (parent != NULL && node->key < parent->key) {
        cutFibonacci(heap, node, parent);
        cascadingCut(heap, parent);
    }
    if (node->key < heap->minimum->key) heap->minimum = node; /* fibonacci decrease key */
}

void deleteFibonacciKey(FibonacciHeap *heap, int key) {
    if (findInCircularList(heap->minimum, key) == NULL) return;
    decreaseFibonacciKey(heap, key, INT_MIN); /* fibonacci delete */
    extractFibonacciMinimum(heap);
}

int main(void) {
    int n, key, oldKey, newKey, removeKey;
    FibonacciHeap heap = {NULL, 0};
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &key);
        insertFibonacci(&heap, key);
    }
    scanf("%d%d%d", &oldKey, &newKey, &removeKey);
    printf("Minimum: %d\n", heap.minimum->key); /* fibonacci find min */
    decreaseFibonacciKey(&heap, oldKey, newKey);
    deleteFibonacciKey(&heap, removeKey);
    printf("Extracted: %d\n", extractFibonacciMinimum(&heap)); /* fibonacci complete */
    return 0;
}

Sample Input

8
10 3 17 8 25 1 12 6
17 2 8

Sample Output

Minimum: 1
Extracted: 1

TRADE-OFFS

⚖️ 7. Heap Comparison

Heap	Representation	Strongest operation	Main cost	Typical use
Binary	Array	Simple extract, cache locality	Union O(n)	Schedulers, standard priority queues
d-ary	Array	Fewer upward levels	More child comparisons	Graph algorithms
Binomial	Forest	Union O(log n)	More pointers	Mergeable queues
Fibonacci	Lazy circular forest	Insert, union, decrease-key O(1) amortized	Complex implementation	Theoretical graph bounds

INTERACTIVE ALGORITHM VISUALIZATION

🎬 8. Premium Heap Visualizer

Choose a heap and operation, then trace comparisons, swaps, linking, consolidation, cuts, root changes and output.

CodeBhavya

KeysNo value requiredHeapOperation

Choose a heap and operation, verify the input and click Load Visualizer.

SELECTABLE C PROGRAM TRACER

🔍 9. Program Tracing — Heaps

Select the heap and operation. The complete matching C program appears with live source highlighting, variables and forest state.

KeysNo value requiredProgramOperation

Select a program and operation, then click Load Program Tracer.

WHERE HEAPS WIN

🧠 10. Applications

CPU / Job Scheduling

Always remove the highest-priority ready job.

Dijkstra and Prim

Repeated extract-min and decrease-key operations drive greedy graph algorithms.

Event Simulation

Process the event with the earliest timestamp.

Top-k and Streaming

Maintain a bounded heap containing the best k values.

DEBUGGING CHECKLIST

⚠️ 11. Common Mistakes

Treating a heap as sorted

Only parent-child order is guaranteed.

Using O(n log n) build

Bottom-up build-heap is O(n).

Repairing only downward

A key change may require bubble-up or heapify-down.

Forgetting binomial degree order

Union must end with one root of each degree.

Eager Fibonacci linking

Insertion and union are lazy; consolidation belongs to extract-min.

Skipping cascading cuts

A marked parent losing another child must also be cut.

CHECK YOUR UNDERSTANDING

✍️ 12. Practice Problems

Solve first, use Hint only when required, then open Show Answer.

1. Where is the minimum stored in a Min-Heap?

2. Is a heap’s array completely sorted?

3. What is the parent of 0-based index i?

4. Why is bottom-up build-heap O(n)?

5. What operation repairs a newly inserted Binary Heap item?

6. What is arbitrary search complexity in a heap?

7. How many nodes are in a binomial tree Bₖ?

8. Why is there at most one binomial root of each degree?

9. What does Binomial Heap union resemble?

10. How does Binomial decrease-key move upward?

11. Which Fibonacci operations are O(1) amortized?

12. When does Fibonacci consolidation occur?

13. What does a Fibonacci mark mean?

14. What triggers a cascading cut?

15. Why can Fibonacci union be O(1)?

16. Which heap is normally simplest and fastest in practice?

17. What is d-ary Heap height?

18. What trade-off appears as d grows?

19. How can delete be reduced to other Min-Heap operations?

20. Which heap gives Dijkstra’s best classic theoretical bound?

QUICK RECALL

📝 13. Quick Revision

A heap guarantees local parent-child priority order, not global sorting.
Binary Heap build is O(n); insert and extract are O(log n); peek is O(1).
Key change repairs upward when priority improves and downward when it worsens.
A d-ary heap trades fewer levels for more comparisons per downward step.
A Binomial Heap has at most one tree of each degree and supports O(log n) union.
A Fibonacci Heap delays consolidation until extract-min.
Fibonacci marks and cascading cuts make decrease-key O(1) amortized.
Binary Heaps are simple and cache-friendly; Fibonacci Heaps optimize theoretical merge/decrease workloads.

⛰️ Heaps and Mergeable Priority Queues

🎯 Learning Objectives

🧭 1. Heap Fundamentals

Min-Heap

Max-Heap

🧰 2. Core Algorithms

🌲 3. Binary Min and Max Heaps

Sample Input

Sample Output

🌿 4. d-ary Heap

🌳 5. Binomial Heap

Union Algorithm

Sample Input

Sample Output

🔥 6. Fibonacci Heap

Decrease-Key with Cascading Cuts

Sample Input

Sample Output

⚖️ 7. Heap Comparison

🎬 8. Premium Heap Visualizer

⛰️ Live Heap State

🔍 9. Program Tracing — Heaps

💻 C Program

🧠 What is happening?

📊 Live Variables

Heap State

Output

🧠 10. Applications

CPU / Job Scheduling

Dijkstra and Prim

Event Simulation

Top-k and Streaming

⚠️ 11. Common Mistakes

Treating a heap as sorted

Using O(n log n) build

Repairing only downward

Forgetting binomial degree order

Eager Fibonacci linking

Skipping cascading cuts

✍️ 12. Practice Problems

1. Where is the minimum stored in a Min-Heap?

2. Is a heap’s array completely sorted?

3. What is the parent of 0-based index i?

4. Why is bottom-up build-heap O(n)?

5. What operation repairs a newly inserted Binary Heap item?

6. What is arbitrary search complexity in a heap?

7. How many nodes are in a binomial tree Bₖ?

8. Why is there at most one binomial root of each degree?

9. What does Binomial Heap union resemble?

10. How does Binomial decrease-key move upward?

11. Which Fibonacci operations are O(1) amortized?

12. When does Fibonacci consolidation occur?

13. What does a Fibonacci mark mean?

14. What triggers a cascading cut?

15. Why can Fibonacci union be O(1)?

16. Which heap is normally simplest and fastest in practice?

17. What is d-ary Heap height?

18. What trade-off appears as d grows?

19. How can delete be reduced to other Min-Heap operations?

20. Which heap gives Dijkstra’s best classic theoretical bound?

📝 13. Quick Revision