What is Max Heap

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


Here's how it works: imagine you have a bunch of numbers and you want to create a max-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 larger than the one on top, you swap them so that the larger number is on top.


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


But that's not all - a max-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 max-heap property. And if you remove the largest number from the heap, the heap will automatically adjust itself so that the next largest number is on top.
​

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

Who invented it?

The concept of a heap is a fundamental data structure in computer science, and the idea of using a binary tree to implement a heap dates back to at least 1964. However, the specific term "max-heap" may have been coined later. It is difficult to attribute the invention of max-heap to a single person or group, as it has been studied and developed by many computer scientists over the years.
One early paper on heaps was "Heap Storage Management in PL/I" by J.W.J. Williams, which was published in the Communications of the ACM journal in 1964. This paper introduced the concept of using a binary tree to store a heap and presented a method for implementing heap operations efficiently.
Another influential paper was "A Simplified Universal Heap Algorithm" by Michael A. Bender and Martin Farach-Colton, which was published in the Journal of the ACM in 1996. This paper presented a simplified version of the heap algorithm that is easier to understand and implement.
Overall, the concept of a max-heap has been developed and refined over many years by numerous computer scientists, and it continues to be an important data structure in computer science today.

Pseudocode

Code Snippet Tabs 

max_heapify(A, i, n):
  left = 2i
  right = 2i + 1
  largest = i
  
  if left <= n and A[left] > A[largest]:
    largest = left
  
  if right <= n and A[right] > A[largest]:
    largest = right
  
  if largest != i:
    swap(A[i], A[largest])
    max_heapify(A, largest, n)

build_max_heap(A):
  n = A.length
  for i from floor(n/2) down to 1:
    max_heapify(A, i, n)
  1. The max_heapify function takes an array A, an index i, and the size of the heap n. It assumes that the binary trees rooted at the left and right children of i are max-heaps, but that the tree rooted at i may violate the max-heap property. It then "fixes" the violation by swapping the root with the largest child (if necessary) and recursively calling max_heapify on the subtree rooted at the largest child.
    The build_max_heap function takes an array A and builds a max-heap by repeatedly calling max_heapify on the subtree rooted at each non-leaf node, starting from the bottom and working up to the root. This ensures that the entire array satisfies the max-heap property.

Sample Code

Code Snippet Tabs 
// C++ code snippet

void max_heapify(int arr[], int n, int i) {
    int largest = i; // Initialize largest as root
    int left = 2*i + 1; // left = 2*i + 1
    int right = 2*i + 2; // right = 2*i + 2

    // If left child is larger than root
    if (left < n && arr[left] > arr[largest])
        largest = left;

    // If right child is larger than largest so far
    if (right < n && arr[right] > arr[largest])
        largest = right;

    // If largest is not root
    if (largest != i) {
        swap(arr[i], arr[largest]);

        // Recursively heapify the affected sub-tree
        max_heapify(arr, n, largest);
    }
}

void heap_sort(int arr[], int n) {
    // Build heap (rearrange array)
    for (int i = n / 2 - 1; i >= 0; i--)
        max_heapify(arr, n, i);

    // One by one extract an element from heap
    for (int i = n - 1; i >= 0; i--) {
        // Move current root to end
        swap(arr[0], arr[i]);

        // call max heapify on the reduced heap
        max_heapify(arr, i, 0);
    }
}

int main() {
    int arr[] = { 12, 11, 13, 5, 6, 7 };
    int n = sizeof(arr)/sizeof(arr[0]);

    heap_sort(arr, n);

    cout << "Sorted array is: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";

    return 0;
}

# Python code snippet


def max_heapify(arr, n, i):
    largest = i  # Initialize largest as root
    left = 2*i + 1  # left = 2*i + 1
    right = 2*i + 2  # right = 2*i + 2

    # If left child is larger than root
    if left < n and arr[left] > arr[largest]:
        largest = left

    # If right child is larger than largest so far
    if right < n and arr[right] > arr[largest]:
        largest = right

    # If largest is not root
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # swap
        # Recursively heapify the affected sub-tree
        max_heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)
    # Build max-heap (rearrange array)
    for i in range(n // 2 - 1, -1, -1):
        max_heapify(arr, n, i)

    # One by one extract an element from heap
    for i in range(n - 1, 0, -1):
        # Move current root to end
        arr[i], arr[0] = arr[0], arr[i]  # swap
        # call max heapify on the reduced heap
        max_heapify(arr, i, 0)

# Example usage
arr = [12, 11, 13, 5, 6, 7]
heap_sort(arr)
print("Sorted array is:", arr)
 

public class HeapSort {

    public static void maxHeapify(int arr[], int n, int i) {
        int largest = i;  // Initialize largest as root
        int left = 2*i + 1;  // left = 2*i + 1
        int right = 2*i + 2;  // right = 2*i + 2

        // If left child is larger than root
        if (left < n && arr[left] > arr[largest])
            largest = left;

        // If right child is larger than largest so far
        if (right < n && arr[right] > arr[largest])
            largest = right;

        // If largest is not root
        if (largest != i) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;

            // Recursively heapify the affected sub-tree
            maxHeapify(arr, n, largest);
        }
    }

    public static void heapSort(int arr[]) {
        int n = arr.length;

        // Build max-heap (rearrange array)
        for (int i = n / 2 - 1; i >= 0; i--)
            maxHeapify(arr, n, i);

        // One by one extract an element from heap
        for (int i = n - 1; i >= 0; i--) {
            // Move current root to end
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // call max heapify on the reduced heap
            maxHeapify(arr, i, 0);
        }
    }

    public static void main(String args[]) {
        int arr[] = {12, 11, 13, 5, 6, 7};

        heapSort(arr);

        System.out.print("Sorted array is: ");
        for (int i = 0; i < arr.length; ++i)
            System.out.print(arr[i] + " ");
    }
}

Time and Space Complexity

  • The time and space complexity of the max-heap algorithm depends on the specific operation being performed.
  • For building a max-heap from an array of size n, the time complexity is O(n), as we need to perform maxHeapify on each node in the tree. Specifically, the maxHeapify method has a time complexity of O(log n), as it takes at most height of the tree to heapify a node.
  • For sorting an array using the max-heap algorithm, the time complexity is O(n log n), as we need to perform maxHeapify n times, and each call to maxHeapify has a time complexity of O(log n). The space complexity is O(1), as the algorithm sorts the input array in-place and doesn't use any additional memory other than a constant number of variables.​

Advantages

  • The max-heap algorithm is a very efficient sorting algorithm, with a time complexity of O(n log n) in the worst case.
  • The algorithm is in-place, meaning that it does not require additional memory proportional to the size of the input array.
  • The max-heap algorithm is stable, meaning that it preserves the relative order of equal elements in the input array.

Disadvantages

  • The max-heap algorithm has a worst-case time complexity of O(n log n), which is not as fast as some other sorting algorithms like quicksort or mergesort. Additionally, the constant factors involved in the max-heap algorithm may make it slower in practice than some other algorithms for small input sizes.
  • The max-heap algorithm has a large number of memory accesses, which can be slow on modern computer architectures due to caching effects.
  • The algorithm is not well-suited to sorting linked lists or other non-array data structures.
Contact Us : [email protected]