What is Min Heap

A min-heap is a special way to store a collection of numbers that allows you to quickly find the smallest number in the collection. It's like having a pile of numbers, but with the smallest one always sitting on top.

Just like with a max-heap, a min-heap is a complete binary tree where each node has a value less than or equal to its children. However, in a min-heap, the smallest value is stored at the root.

Here's how it works: imagine you have a bunch of numbers and you want to create a min-heap. You start by putting the first number in the heap. Then, for each subsequent number, you compare it to the number on top of the heap. If the new number is smaller than the one on top, you swap them so that the smaller number is on top.

You keep doing this for every number in the collection, so that when you're finished, the smallest number will be sitting at the top of the heap. This makes it very easy and efficient to find the minimum number in the collection - you just look at the top of the heap!

Just like with a max-heap, a min-heap also has some other useful properties. For example, if you add a new number to the heap, it will automatically be placed in the correct location to maintain the min-heap property. And if you remove the smallest number from the heap, the heap will automatically adjust itself so that the next smallest number is on top.

Overall, a min-heap is a very powerful algorithm for efficiently storing and retrieving the smallest element in a collection of numbers.

Who invented it?

The concept of the min heap data structure has been around for a long time, and its origins are not well-documented. However, the modern definition and implementation of the min heap data structure can be attributed to a number of researchers in computer science and mathematics.
One of the earliest references to the min heap data structure was made by John Williams in 1964, in his paper "Algorithm 232: Heapsort". In this paper, Williams introduced the idea of using a heap data structure for sorting elements, and presented an algorithm for implementing heapsort using a binary min heap.

Another important contribution to the development of the min heap data structure was made by Donald Knuth in his seminal work "The Art of Computer Programming", where he discussed the properties and implementation of binary heaps in detail. Knuth's work helped to establish the binary heap as a fundamental data structure in computer science.

Other notable researchers who have contributed to the development and refinement of the min heap data structure include Jon Bentley, Robert Floyd, and Tony Hoare. Today, the min heap is a widely-used data structure in computer science and is an important building block for many algorithms and applications.

Pseudocode

Code Snippet Tabs



// function to heapify a subtree rooted at index i in an array a of size n
heapify(a, n, i):
    smallest = i  // initialize smallest as root
    left = 2*i + 1  // index of left child
    right = 2*i + 2  // index of right child
    
    // if left child is smaller than root, set smallest to left child
    if left < n and a[left] < a[smallest]:
        smallest = left
        
    // if right child is smaller than smallest, set smallest to right child
    if right < n and a[right] < a[smallest]:
        smallest = right
    
    // if smallest is not root, swap the smallest element with the root
    if smallest != i:
        swap(a[i], a[smallest])
        heapify(a, n, smallest)
        
// function to build a binary min heap from an array a of size n
build_min_heap(a, n):
    // start from the last non-leaf node and heapify each node in reverse order
    for i from floor(n/2)-1 down to 0:
        heapify(a, n, i)

// function to insert a new element key into a binary min heap a of size n
insert_key(a, n, key):
    n = n + 1
    i = n - 1
    a[i] = key
    
    // fix the min-heap property by swapping the new element with its parent until the property is restored
    while i != 0 and a[(i-1)/2] > a[i]:
        swap(a[i], a[(i-1)/2])
        i = (i-1)/2

// function to extract the minimum element from a binary min heap a of size n
extract_min(a, n):
    if n == 0:
        return NULL
        
    // remove the minimum element (which is at the root) and replace it with the last element in the heap
    if n == 1:
        n = n - 1
        return a[0]
    
    root = a[0]
    a[0] = a[n-1]
    n = n - 1
    
    // restore the min-heap property by heapifying the new root
    heapify(a, n, 0)
    
    return root

heapify() function: This function takes three arguments - an array a representing the heap, its size n, and the index i of the node to be heapified. The purpose of heapify() is to restore the min-heap property for the subtree rooted at index i.
build_min_heap() function: This function takes an array a representing the heap and its size n as arguments, and builds a binary min heap from the elements in the array. The build_min_heap() function works by repeatedly calling heapify() on each non-leaf node in reverse order of their indices, starting from the last non-leaf node.
insert_key() function: This function takes an array a representing the heap, its size n, and the new key to be inserted into the heap. The insert_key() function works by adding the new key to the end of the heap, then repeatedly swapping the new key with its parent until the min-heap property is restored.
extract_min() function: This function takes an array a representing the heap and its size n as arguments, and returns the minimum element in the heap. The extract_min() function works by removing the minimum element (which is at the root of the heap) and replacing it with the last element in the heap. The function then restores the min-heap property by heapifying the new root.

Overall, the binary min heap is a data structure that maintains the property that the minimum element in the heap is always stored at the root. The heapify operation is used to ensure that this property is maintained after inserting or deleting elements from the heap.

Sample Code

Code Snippet Tabs

C++
Python
Java

// C++ code snippet

// heapify a subtree rooted at index i
void heapify(vector& a, int n, int i) {
    int smallest = i;
    int left = 2*i + 1;
    int right = 2*i + 2;
    
    if (left < n && a[left] < a[smallest]) {
        smallest = left;
    }
    
    if (right < n && a[right] < a[smallest]) {
        smallest = right;
    }
    
    if (smallest != i) {
        swap(a[i], a[smallest]);
        heapify(a, n, smallest);
    }
}

// build a binary min heap from an array
void build_min_heap(vector& a, int n) {
    for (int i = (n/2)-1; i >= 0; i--) {
        heapify(a, n, i);
    }
}

// insert a key into the binary min heap
void insert_key(vector& a, int& n, int key) {
    a.push_back(key);
    n++;
    int i = n-1;
    while (i > 0 && a[(i-1)/2] > a[i]) {
        swap(a[i], a[(i-1)/2]);
        i = (i-1)/2;
    }
}

// extract the minimum element from the binary min heap
int extract_min(vector& a, int& n) {
    if (n <= 0) {
        return -1;
    }
    
    int root = a[0];
    a[0] = a[n-1];
    n--;
    heapify(a, n, 0);
    return root;
}

int main() {
    vector heap {10, 20, 15, 40, 50, 100, 25};
    int n = heap.size();
    
    // build the min heap
    build_min_heap(heap, n);
    
    // insert a new key
    int key = 12;
    insert_key(heap, n, key);
    
    // extract the minimum element
    int min = extract_min(heap, n);
    
    // print the resulting heap and the extracted minimum element
    cout << "Heap: ";
    for (int i = 0; i < n; i++) {
        cout << heap[i] << " ";
    }
    cout << endl;
    
    cout << "Minimum element extracted: " << min << endl;
    
    return 0;
}

# Python code snippet


import sys

# heapify a subtree rooted at index i
def heapify(a, n, i):
    smallest = i
    left = 2*i + 1
    right = 2*i + 2
    
    if left < n and a[left] < a[smallest]:
        smallest = left
    
    if right < n and a[right] < a[smallest]:
        smallest = right
    
    if smallest != i:
        a[i], a[smallest] = a[smallest], a[i]
        heapify(a, n, smallest)

# build a binary min heap from an array
def build_min_heap(a, n):
    for i in range(n//2-1, -1, -1):
        heapify(a, n, i)

# insert a key into the binary min heap
def insert_key(a, n, key):
    a.append(key)
    n += 1
    i = n-1
    while i > 0 and a[(i-1)//2] > a[i]:
        a[i], a[(i-1)//2] = a[(i-1)//2], a[i]
        i = (i-1)//2

# extract the minimum element from the binary min heap
def extract_min(a, n):
    if n <= 0:
        return -sys.maxsize - 1
    
    root = a[0]
    a[0] = a[n-1]
    n -= 1
    heapify(a, n, 0)
    return root

# driver code
a = [10, 20, 15, 40, 50, 100, 25]
n = len(a)

# build the min heap
build_min_heap(a, n)

# insert a new key
key = 12
insert_key(a, n, key)

# extract the minimum element
min_elem = extract_min(a, n)

# print the resulting heap and the extracted minimum element
print("Heap: ", end="")
for i in range(n):
    print(a[i], end=" ")
print()

print("Minimum element extracted: ", min_elem)


import java.util.Arrays;

public class MinHeap {
    private int[] heap;
    private int size;
    private int capacity;

    public MinHeap(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.heap = new int[capacity];
    }

    private void heapify(int[] a, int n, int i) {
        int smallest = i;
        int left = 2*i + 1;
        int right = 2*i + 2;

        if (left < n && a[left] < a[smallest]) {
            smallest = left;
        }

        if (right < n && a[right] < a[smallest]) {
            smallest = right;
        }

        if (smallest != i) {
            int temp = a[i];
            a[i] = a[smallest];
            a[smallest] = temp;
            heapify(a, n, smallest);
        }
    }

    private void buildMinHeap() {
        for (int i = size/2 - 1; i >= 0; i--) {
            heapify(heap, size, i);
        }
    }

    public void insertKey(int key) {
        if (size == capacity) {
            System.out.println("Overflow: Heap is full");
            return;
        }
        size++;
        int i = size - 1;
        heap[i] = key;

        while (i > 0 && heap[(i-1)/2] > heap[i]) {
            int temp = heap[i];
            heap[i] = heap[(i-1)/2];
            heap[(i-1)/2] = temp;
            i = (i-1)/2;
        }
    }

    public int extractMin() {
        if (size <= 0) {
            System.out.println("Underflow: Heap is empty");
            return -1;
        }

        int root = heap[0];
        heap[0] = heap[size-1];
        size--;
        heapify(heap, size, 0);
        return root;
    }

    public void printHeap() {
        System.out.print("Heap: ");
        for (int i = 0; i < size; i++) {
            System.out.print(heap[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        MinHeap heap = new MinHeap(10);

        heap.insertKey(10);
        heap.insertKey(20);
        heap.insertKey(15);
        heap.insertKey(40);
        heap.insertKey(50);
        heap.insertKey(100);
        heap.insertKey(25);

        heap.buildMinHeap();

        heap.insertKey(12);

        heap.printHeap();

        int min = heap.extractMin();

        heap.printHeap();

        System.out.println("Minimum element extracted: " + min);
    }
}

Time and Space Complexity

The time complexity of most of the basic operations of a binary min heap, including insertion, extraction of the minimum element, and building a min heap from an array, is O(log n), where n is the number of elements in the heap.
The time complexity of initializing a heap with n elements using heapify is O(n), but this operation is usually only performed once at the beginning.
The space complexity of a min heap is O(n), where n is the number of elements in the heap, since the heap is stored as an array of size n.

Advantages

The minimum element can be accessed in constant time O(1).
Insertion and deletion of elements have a worst-case time complexity of O(log n), making it an efficient data structure for maintaining a sorted list of elements.
Building a min heap from an unordered array can be done in linear time O(n).
It can be implemented using an array, which saves space compared to a linked list-based implementation.

Disadvantages

Finding the ith smallest element requires O(i log n) time complexity, which can be inefficient for large values of i.
Unlike a binary search tree, a binary heap does not provide efficient support for searching for a specific element.
Elements in the heap must have a total ordering, which may not be suitable for all types of data.
In summary, the binary min heap is a useful data structure when fast access to the minimum element is required, and when the ability to insert and delete elements efficiently is important. However, it may not be the best choice for all situations and data types.

< Hiring Assistant

Heap Sort >