Introduction to Heaps

A heap is a special tree-based data structure that satisfies the heap property. In a max heap, for any given node, the value of the node is greater than or equal to the values of its children, and in a min heap, the value of the node is less than or equal to the values of its children. Heaps are commonly used in priority queues, sorting algorithms, and graph algorithms like Dijkstra's shortest path.

Types of Heaps

1. Binary Heap

A binary heap is a complete binary tree that satisfies the heap property. It can be either a max heap or a min heap.

void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2*i + 1;
    int right = 2*i + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;

    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        std::swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void insert(int arr[], int &n, int value) {
    n++;
    arr[n-1] = value;

    for (int i = n/2 - 1; i >= 0; i--)
        heapify(arr, n, i);
}

void deleteRoot(int arr[], int &n) {
    if (n <= 0)
        return;
    
    arr[0] = arr[n-1];
    n--;
    heapify(arr, n, 0);
}
            

Use Cases: Implementing priority queues, heap sort, scheduling tasks, finding the k-th largest or smallest element.

2. Min Heap

A min heap is a type of binary heap where the value of the root node is less than or equal to the values of its children. This property applies recursively to all nodes in the heap.

void minHeapify(int arr[], int n, int i) {
    int smallest = i;
    int left = 2*i + 1;
    int right = 2*i + 2;

    if (left < n && arr[left] < arr[smallest])
        smallest = left;

    if (right < n && arr[right] < arr[smallest])
        smallest = right;

    if (smallest != i) {
        std::swap(arr[i], arr[smallest]);
        minHeapify(arr, n, smallest);
    }
}

void insertMinHeap(int arr[], int &n, int value) {
    n++;
    arr[n-1] = value;

    for (int i = n/2 - 1; i >= 0; i--)
        minHeapify(arr, n, i);
}

void deleteRootMinHeap(int arr[], int &n) {
    if (n <= 0)
        return;

    arr[0] = arr[n-1];
    n--;
    minHeapify(arr, n, 0);
}
            

Use Cases: Implementing priority queues where the smallest element is needed, Dijkstra's shortest path algorithm, and median-finding algorithms.

3. Fibonacci Heap

A Fibonacci heap is an advanced heap data structure that provides more flexibility and efficiency compared to binary heaps, especially in the context of operations like decrease-key and delete. It is named after the Fibonacci sequence because its structure and performance analysis are closely related to Fibonacci numbers. Unlike binary heaps, Fibonacci heaps allow trees within the heap to be unbalanced, leading to a more relaxed and efficient structure. This flexibility enables certain operations to be performed in constant amortized time, making Fibonacci heaps highly efficient for specific applications, particularly in graph algorithms.

The fundamental components of a Fibonacci heap are a collection of heap-ordered trees. In these trees, the minimum key is always at the root of one of the trees, and the heap maintains a pointer to this minimum node, enabling quick access to the minimum element. The trees within the Fibonacci heap are not necessarily binary; they can have any number of children, and the trees are linked together in a circular doubly linked list.

Key Features of Fibonacci Heaps:

1. Lazy Merging: Unlike other heap structures where trees are merged immediately after operations, Fibonacci heaps delay this merging process. This lazy merging strategy contributes to the heap's efficiency in supporting decrease-key and delete operations. As a result, insertions and other operations that do not directly require tree merging can be performed very quickly.
2. Amortized Time Complexity: Fibonacci heaps are designed to provide very efficient amortized time complexity for several key operations. For example, insert, find-min, and decrease-key operations have an amortized time complexity of O(1). The delete and extract-min operations have an amortized time complexity of O(log n), which is still very efficient for large datasets.
3. Tree Structure and Degrees: The trees in a Fibonacci heap are ordered by degree, where the degree of a node is the number of its children. As nodes are linked together, the trees are consolidated, leading to a structure where each tree has a unique degree. The maximum degree of any node is O(log n), which limits the number of trees in the heap and ensures efficient operations.
4. Decrease-Key Operation: One of the most powerful features of a Fibonacci heap is its ability to perform the decrease-key operation in constant time. When the key of a node decreases, the node may need to be cut from its current position and reinserted as a new root, leading to a potential cascading cut. This ensures the tree remains balanced while maintaining the heap properties.
5. Consolidation Process: After an extract-min operation, the trees in the heap are consolidated to ensure that each tree has a unique degree. This process involves linking trees of the same degree until no two trees have the same degree. The result is a collection of well-structured trees that maintain the heap's efficiency.

The flexibility and efficiency of Fibonacci heaps make them particularly useful in graph algorithms that require frequent decrease-key operations. For example, in Dijkstra's shortest path algorithm and Prim's minimum spanning tree algorithm, the decrease-key operation is frequently used to update the distance or weight of nodes. The efficient handling of these operations by Fibonacci heaps leads to significant performance improvements in these algorithms, especially when dealing with dense graphs or large datasets.

However, the complexity of implementing Fibonacci heaps, along with their relatively high constant factors for certain operations, means they are typically used in theoretical contexts or in applications where their specific advantages outweigh the implementation complexity. Despite this, Fibonacci heaps remain an important data structure in the study of algorithms and data structures, providing valuable insights into the design of efficient algorithms.

The diagram below illustrates the structure of a Fibonacci heap, showing how trees of different degrees are linked together and how the minimum node is maintained:

struct FibonacciNode {
    int data;
    FibonacciNode* parent;
    FibonacciNode* child;
    FibonacciNode* left;
    FibonacciNode* right;
    int degree;
    bool mark;
};

void insertNode(FibonacciNode* &minNode, int value) {
    FibonacciNode* newNode = new FibonacciNode();
    newNode->data = value;
    newNode->degree = 0;
    newNode->parent = newNode->child = nullptr;
    newNode->left = newNode->right = newNode;
    newNode->mark = false;

    if (minNode != nullptr) {
        minNode->left->right = newNode;
        newNode->right = minNode;
        newNode->left = minNode->left;
        minNode->left = newNode;

        if (value < minNode->data)
            minNode = newNode;
    } else {
        minNode = newNode;
    }
}

// Fibonacci heap operations like extract-min, decrease-key, and delete are complex and involve cutting and cascading cuts to maintain the heap's properties.
            

Use Cases: Efficient graph algorithms, especially where frequent decrease-key operations are needed, such as in Dijkstra's and Prim's algorithms.

Heap Operations

1. Insertion

Insertion in heaps involves adding the new element at the end of the heap and then "heapifying" the heap to maintain the heap property.

void insert(int arr[], int &n, int value) {
    n++;
    arr[n-1] = value;

    for (int i = n/2 - 1; i >= 0; i--)
        heapify(arr, n, i);
}
            

2. Deletion

Deletion in heaps typically refers to deleting the root (the max or min element), replacing it with the last element, and then heapifying to maintain the heap property.

void deleteRoot(int arr[], int &n) {
    if (n <= 0)
        return;

    arr[0] = arr[n-1];
    n--;
    heapify(arr, n, 0);
}
            

3. Peek

The peek operation returns the root of the heap (the max or min element) without removing it.

int peek(int arr[]) {
    return arr[0];
}
            

4. Heapify

Heapify is a fundamental process in the management of heaps, specifically in converting a binary tree into a valid heap structure, either a max heap or a min heap. The goal of heapify is to ensure that the heap property is maintained throughout the tree. The heap property for a max heap dictates that every parent node must be greater than or equal to its child nodes, while for a min heap, every parent node must be less than or equal to its child nodes. This property must hold true across the entire tree for it to be considered a valid heap.

The heapify process typically begins from the bottommost and rightmost internal node (non-leaf node) and works its way up to the root of the tree. The reason for starting at the bottom is that leaf nodes trivially satisfy the heap property, and any violation of the heap property is more likely to occur at the internal nodes that have children.

The process is usually implemented as a recursive or iterative function that examines a node and its children, making adjustments as necessary to ensure the heap property is maintained. Here’s how the heapify process works in detail:

Step-by-Step Heapify Process:

1. Identify the Node: Starting from the bottommost and rightmost internal node, compare this node with its left and right children (if they exist).
2. Find the Largest (or Smallest) Value: In a max heap, identify the largest value among the node and its children. In a min heap, identify the smallest value. This value will be the candidate for the potential swap.
3. Swap if Necessary: If the parent node does not already satisfy the heap property (i.e., if in a max heap the parent node is smaller than one of its children, or in a min heap the parent node is larger than one of its children), swap the parent node with the largest (or smallest) of its children.
4. Recursive Heapify: After the swap, the child node (which has now moved up) may violate the heap property with its own children. Recursively apply the heapify process to the affected subtree, ensuring that the heap property is maintained throughout the tree.
5. Continue Up the Tree: Move to the next node up (in a level-order traversal sense) and repeat the process. This is done iteratively or recursively until the root node is reached and the entire tree satisfies the heap property.

The overall time complexity of the heapify operation is O(log n) because, in the worst case, the heapify process may traverse from the node to the root, which is proportional to the height of the tree. Since a heap is a complete binary tree, its height is log n, making the heapify operation efficient.

This process is critical in the construction of a heap, such as when building a heap from an unsorted array (commonly done in heap sort). It is also used in the maintenance of the heap structure during insertion and deletion operations, ensuring that the tree remains a valid heap after any modification.

The diagram below illustrates how the heapify process adjusts nodes in a binary tree to maintain the max heap property:

void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2*i + 1;
    int right = 2*i + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;

    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        std::swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

When to Use Different Types of Heaps

Heaps are versatile and can be used in a variety of scenarios depending on their type:

1. Binary Heap

Use Cases: Ideal for implementing priority queues, where quick access to the largest or smallest element is required. Commonly used in heap sort, task scheduling, and graph algorithms.

2. Min Heap

Use Cases: Best suited for scenarios where the smallest element needs to be accessed frequently, such as in Dijkstra's shortest path algorithm or in implementing priority queues with the smallest element at the top.

3. Fibonacci Heap

Use Cases: Used in advanced algorithms like Dijkstra's and Prim's algorithms, where decrease-key and delete operations are frequent, and their amortized time complexity benefits the overall efficiency of the algorithm.