Min Heap Using Linked Nodes

Overview

This project implements a min heap using linked nodes rather than an array. It focuses on conceptual understanding of how heap operations maintain both shape and order properties in a tree structure.

A min heap satisfies two main conditions:

Property	Description
Structural Property	The tree is complete, meaning all levels are filled except possibly the last, which is filled from left to right.
Order Property	Each parent node’s key is less than or equal to the keys of its children.

Example of a valid min heap:

       2
     /   \
    4     5
   / \   /
  7   9  8

Node Structure

Each node stores a key-value pair and links to its children and parent.

template <typename K, typename V>
class Node {
public:
    K key;
    V value;
    Node* left;
    Node* right;
    Node* parent;

    Node(K k, V v)
        : key(k), value(v), left(nullptr), right(nullptr), parent(nullptr) {}
};

Heap Class Overview

The Heap class keeps track of the root node and provides core operations:

Operation	Description
insert(key, value)	Adds a new node while maintaining completeness, then calls heapify() to restore order.
getMin()	Returns the smallest key, which is always at the root.
deleteMin()	Removes the root, replaces it with the last node, and calls heapify() to restore order.
heapify(Node* node)	Recursively restores heap order from the bottom up.

Insert Operation

Step 1. Add the New Node

Insertion happens at the next available position in level order to maintain the complete tree property.

Example before inserting 3:

     2
   /   \
  4     5
 / \
7   9

After inserting 3:

     2
   /   \
  4     5
 / \   /
7   9  3

Step 2. Restore Order with heapify()

After insertion, heapify() is called starting from the root. It traverses the tree in postorder (left → right → node) and swaps values where necessary to maintain the min heap property.

During heapify:

• The subtree rooted at node 5 violates the heap property because 3 < 5.
• The two nodes swap their key-value pairs.

Resulting heap:

     2
   /   \
  4     3
 / \   /
7   9  5

Now the heap property is restored.

How heapify() Works

The recursive version of heapify() traverses the tree from the leaves upward.

void heapify(Node<K,V>* node) {
    if (!node) return;

    heapify(node->left);
    heapify(node->right);

    Node<K,V>* smallest = node;

    if (node->left && node->left->key < smallest->key)
        smallest = node->left;
    if (node->right && node->right->key < smallest->key)
        smallest = node->right;

    if (smallest != node) {
        swapNodeData(node, smallest);
        heapify(smallest);
    }
}

Step-by-step

1. Visit the left subtree.
2. Visit the right subtree.
3. Compare the node with its children.
4. Swap data if the node is greater than a child.
5. Recurse into the affected child to continue fixing the heap.

This ensures that all subtrees become valid heaps before checking their parent nodes.

DeleteMin Operation

Step 1. Remove the Root

The minimum value is always at the root. To delete it, replace the root’s data with the data from the last node (the deepest, rightmost node).

Before deleting min (2):

     2
   /   \
  4     3
 / \   /
7   9  5

Replace 2 with 5:

     5
   /   \
  4     3
 / \
7   9

Step 2. Restore Order with heapify()

Heapify is called on the root to restore the order property.

• Compare 5 with its children (4 and 3).
• 3 is the smallest, so swap 5 and 3.

Resulting heap:

     3
   /   \
  4     5
 / \
7   9

Now the heap property is satisfied again.

Visualizing Heapify

heapify() works in a postorder traversal pattern:

        (node)
        /   \
   heapify(L) heapify(R)
        |
   Compare node and children
        |
     Swap if needed
        |
   heapify(child)

This guarantees that children are already in correct order before comparing with their parent.

Summary

Operation	Behavior	Restores Order By
insert()	Adds node in next open position	Calls heapify(root)
deleteMin()	Replaces root with last node and removes the last	Calls heapify(root)
heapify()	Traverses the tree bottom-up, fixing order violations	Recursive postorder traversal

Time Complexity

Operation	Time Complexity	Explanation
insert()	O(n)	Because heapify(root) traverses the whole tree in this linked version.
deleteMin()	O(n)	Same reason as insertion.
heapify()	O(n)	Processes every node once during traversal.

Teaching Notes

• The linked structure helps students visualize the heap as a true tree rather than an array.
• Each insertion and deletion reinforces how both shape and order must be maintained.
• The recursive heapify() approach clearly demonstrates bottom-up correction before introducing more efficient array-based heaps.