Exploring Time and Space Complexities of Heap Operations

A heap is a binary tree-based data structure where each parent node satisfies a specific order property relative to its children (min-heap or max-heap).

There are two main heap operations:

1. Heapify
2. Extract Minimum (from min-heap) or Extract Maximum (from max-heap)

Since our DSA courses use min-heaps instead of max-heaps, this article will only explore the Heapify and Extract Minimum operations.

Heapify

Heapify is a process that transforms a binary tree into a heap by adjusting the elements to maintain the heap property.

This operation ensures that every parent node is greater than or equal to (max-heap), or less than or equal to (min-heap), its children.

def heapify(self, array):
    # Initialize the heap with the given array
    self.heap = array
    # Start from the last index and move backward,
    # performing heapify-down operation on each node
    for i in range(len(self.heap) - 1, -1, -1):
        self.heapify_down(i)

def heapify_down(self, index):
    # If we reach a leaf node,
    # end the process
    if not self.has_left_child(index):
        return

    # Assume the left child is the smaller child
    smaller_child_index = self.left_child(index)

    # If the right child is smaller than the left child,
    # update smaller_child_index to the right child's index
    if self.has_right_child(index) and self.heap[self.right_child(index)] < self.heap[smaller_child_index]:
        smaller_child_index = self.right_child(index)

    # If the current node is smaller or equal to the smaller child,
    # no further action is needed, so end the process
    if self.heap[index] <= self.heap[smaller_child_index]:
        return

    # Swap the current node with the smaller child
    # and recursively call heapify_down on the smaller child's index
    self.swap(index, smaller_child_index)
    self.heapify_down(smaller_child_index)

// Heapify down from a given index
void heapify(int index) {
    // If we reach a leaf node,
    // end the process
    if (!has_left_child(index)) {
        return;
    }

    // Assume the left child is the smaller child
    int smaller_child_index = left_child(index);

    // If the right child is smaller than the left child,
    // update smaller_child_index to the right child's index
    if (has_right_child(index) && heap[right_child(index)] < heap[smaller_child_index]) {
        smaller_child_index = right_child(index);
    }

    // If the current node is smaller or equal to the smaller child,
    // no further action is needed, so end the process
    if (heap[index] <= heap[smaller_child_index]) {
        return;
    }

    // Swap the current node with the smaller child and
    // recursively call heapify() on the smaller child's index
    swap(index, smaller_child_index);
    heapify(smaller_child_index);
}

Time Complexity of Heapify

Best Case Time Complexity: O(1)

The best case time complexity occurs when the subtree rooted at the given node already satisfies the heap property. No swaps are required, and the function exits immediately.

For example, consider the tree below:

If we call heapify() starting from the root (5), no swaps are needed since 5 is already smaller than both its children (10 and 15). Thus, the function exits immediately.

Worst Case Time Complexity: O(logn)

The worst case time complexity occurs when the subtree needs adjustments at every level of the tree.

Starting from the root node, the function may traverse down to the leaf node. This leads to a time complexity of O(logn) since the tree's height is logn.

Average Case Time Complexity: O(logn)

On average, heapify operates in O(logn), as it typically adjusts a few levels of the binary tree to maintain the heap property.

Space Complexity of Heapify: O(1)

Heapify operates in-place, meaning it does not require additional space for temporary arrays or structures. Only a few variables for index tracking are used, making its space complexity constant.

Hence, the space complexity is O(1).

Summary: Complexity Analysis of Heapify

Extract the Minimum Element

Extracting the minimum element from a binary heap involves removing the root element (the smallest in a min-heap) and rebalancing the heap.

import heapq

def extract_min(heap):
    # Remove and return the smallest element
    return heapq.heappop(heap)

#include <queue>
#include <vector>
#include <stdexcept>
using namespace std;

int extract_min(priority_queue<int, vector<int>, greater<int>>& heap) {
    // Retrieve the smallest element
    int min_element = heap.top();
    // Remove it from the heap
    heap.pop();
    return min_element;
}

Time Complexity of Extracting Min

The time complexity of the extraction process is influenced by the following stages of the operation:

1. Removing Root Element

This is a straightforward process that takes a constant time complexity of O(1).

2. Rebalancing the Heap

The last element is moved to the root, and the heap property is restored using the heapify operation, which has a time complexity of O(logn).

Overall Time Complexity: O(logn)

Therefore, the overall time complexity of extracting the min element from a heap is O(logn).

Space Complexity of Extracting Min: O(1)

The operation is performed in-place, requiring no additional memory apart from temporary variables.

Hence, the space complexity of extracting min is O(1).

Summary