MaxHeapSort

Introduction to MaxHeapSort

MaxHeapSort is a sorting algorithm that operates on a data structure called a max heap. It is an efficient algorithm for sorting elements in ascending order. In MaxHeapSort, the largest element is repeatedly extracted from the max heap and placed at the end of the sorted array. The heap is then restructured to maintain the heap property, and the process is repeated until all elements are sorted.

MaxHeapSort has a time complexity of O(n log n), making it suitable for sorting large datasets. It is commonly used in various applications where sorting is required.

Overview of MaxHeapSort

MaxHeapSort is a sorting algorithm that operates on a data structure called a max heap. It is known for its efficiency in sorting elements in ascending order. The algorithm repeatedly extracts the largest element from the max heap and places it at the end of the sorted array. This process continues until all elements are sorted. MaxHeapSort has a time complexity of O(n log n), making it a suitable choice for sorting large datasets. It is widely used in various applications that require sorting.

Code(Python):


""" Copyrights to venkys.io
For more information, visit https://venkys.io """

# Python program for performing Breadth First Search

# Space complexity: O(log n)
# Time complexity: O(n log n) 

# Function to maintain max heap properties
def VSDmaxHeapify(arr,size,i):

    #declare current element index is largest element
    large=i 
    #find index of left child
    leftchild=(2*i)+1 
    #find index of right child
    rightchild=(2*i)+2 
    # check largest element between left child and current element
    if leftchild<size and arr[i]<arr[leftchild]:
        large=leftchild
 
    # check largest element between right child and large element
    if rightchild<size and arr[large]<arr[rightchild]:
        large=rightchild
    
    # if large element is not current element 
    # swap current element with large element 
    # heapify the the current array
    if large!=i:
        arr[large],arr[i]=arr[i],arr[large]
        VSDmaxHeapify(arr,size,large)

# Function to maintain max heap properties
def VSDminHeapify(arr,size,i):
    
    #Declare the current element index as smallest
    small=i

    #Find the index of leftchild element
    leftchild=(2*i)+1

    #Find the index of rightchild element
    rightchild=(2*i)+2

    #Check the smallest element between leftchild and current element
    if leftchild<size and arr[i]>arr[leftchild]:
        small=leftchild
    
    #Check the smallest element between rightchild and smallest element
    if rightchild<size and arr[small]>arr[rightchild]:
        small=rightchild
    
    # If smallest element is not current element
    # Swap the smallest element and current element
    # Heapify the current array
    if small!=i:
        arr[small],arr[i]=arr[i],arr[small]
        VSDminHeapify(arr,size,small)

# Function to insert elements into max heap
def insert(array,num):
    if len(array)==0:
        array.append(num)
    else:
        array.append(num)
        for i in range(len(array)):
            VSDmaxHeapify(array,len(array),i)

# Function to sort the given array using maxheap in ascending order
def VSDMaxheapsort(array):
    size=len(array)

    # Heapify the given array into maxheap
    for i in range((size//2)-1,-1,-1):
        VSDmaxHeapify(array,size,i)

    # Find the max element in array
    # Swap the max element with last index element 
    # Decrease the last index by 1
    # Heapify the current array upto last index
    for i in range(size-1,0,-1):
        array[i],array[0]=array[0],array[i]
        VSDmaxHeapify(array,i,0)
  

# Function to sort the given array using minheap in descending order
def VSDMinheapsort(array):
    size=len(array)

    # Heapify the given array into min heap
    for i in range((size//2)-1,-1,-1):
        VSDminHeapify(array,size,i)
    
    # Find the min element in array
    # Swap the min element with last index element
    # Decrease the last index by 1
    # Heapify the current array upto last index
    for i in range(size-1,-1,-1):
        array[0],array[i]=array[i],array[0]
        VSDminHeapify(array,i,0)

#Fucntion to print array
def printarray(array):

    for i in array:
        print(i,end=" ")
    print()

if __name__ == "__main__":
    # Taking input for the array from the user
    input_str = input("Enter the array elements separated by space: ")
    arr = list(map(int, input_str.split()))

    print("Original array:")
    printarray(arr)

    # Sorting using max heap
    print("Sorted array using maxheapsort:")
    VSDMaxheapsort(arr)
    printarray(arr)

    # Sorting using min heap
    print("Sorted array using minheapsort:")
    VSDMinheapsort(arr)
    printarray(arr)

Step-by-step Explaination:

The code provided demonstrates the implementation of the MaxHeapSort algorithm in Python. Here is a step-by-step explanation of how the algorithm works:

The VSDmaxHeapify function is defined to maintain the max heap properties. It takes three parameters: the array, the size of the heap, and the index of the current element.
The VSDminHeapify function is defined to maintain the min heap properties. It takes the same parameters as VSDmaxHeapify.
The insert function is defined to insert elements into the max heap. It takes the array and the number to be inserted as parameters.
The VSDMaxheapsort function is defined to sort the given array using the max heap. It first heapifies the array into a max heap. Then, it repeatedly swaps the maximum element with the last element in the array, reduces the size of the array by 1, and heapifies the remaining array.
The VSDMinheapsort function is defined to sort the given array using the min heap. It follows a similar process as VSDMaxheapsort, but maintains the min heap properties instead.
The printarray function is defined to print the elements of an array.
In the main program, an example array arr is created with some random elements.
The VSDMaxheapsort function is called to sort the array in ascending order using the max heap.
The sorted array is printed using the printarray function.
The VSDMinheapsort function is called to sort the array in descending order using the min heap.
The sorted array is printed again.

This is a basic overview of how the MaxHeapSort algorithm works. The provided code demonstrates the implementation and usage of the algorithm in Python.

Code(Java):


/* Copyrights to venkys.io
For more information, visit https://venkys.io */

// Space complexity: O(log n)
// Time complexity: O(n log n)
import java.util.Scanner;

public class maxsort {
    // Class to hold the structure of a node in a tree
    public static class Node {
        int data; // Holds the value of the node
        Node left; // Holds the left pointer of the node
        Node right; // Holds the right pointer of the node

        // Default constructor
        Node(int data) {
            this.data = data;
            this.left = this.right = null;
        }
    }

    // Root node
    public static Node root = null;

    // Variable to hold the count of left nodes
    public static int leftcount = 0;

    // Variable to hold the count of right nodes
    public static int rightcount = 0;

    // Variable to maintain the count of nodes in the heap for appropriate deletion
    public static int deletecount = 0;

    // Variable to hold the appropriate child node for deletion
    public static Node deletenode = null;

    // Variable to hold the parent of the child to be deleted
    public static Node parent = null;

    // Method to Build Heap along with maintenance of a complete binary tree
    public static Node VSDbuildHeap(Node root, Node newNode) {
        if (root == null)
            root = newNode; // Null check
        else if (root.left != null && root.right != null) // Checking whether both left and right children are present
                                                            // for the root
        {
            leftcount = VSDsubtreeCount(root.left); // Getting left nodes count from the left of the current root
            rightcount = VSDsubtreeCount(root.right); // Getting right nodes count from the right of the current root

            int height = VSDfindHeight(root); // Getting the height of the tree
            // Checking for the correct position to insert
            if (leftcount < (VSDexpectedCount(height) / 2)) {
                VSDbuildHeap(root.left, newNode);
            } else if (leftcount == rightcount)
                VSDbuildHeap(root.left, newNode);
            else
                VSDbuildHeap(root.right, newNode);
        } else if (root.left == null) {
            root.left = newNode;

        } else if (root.right == null) {
            root.right = newNode;

        }

        return root;
    }

    // Function to maintain max heap properties
    public static Node VSDHeapify(Node current) {
        if (current.left != null)
            current.left = VSDHeapify(current.left);
        if (current.right != null)
            current.right = VSDHeapify(current.right);
        if (current.left != null && current.left.data > current.data) {
            int temp = current.left.data;
            current.left.data = current.data;
            current.data = temp;

        }
        if (current.right != null && current.right.data > current.data) {
            int temp = current.right.data;
            current.right.data = current.data;
            current.data = temp;
        }
        return current;
    }

    // Function to return the expected node count for a given height
    public static int VSDexpectedCount(int h) {
        int count = 0;
        while (h >= 0) {
            count += Math.pow(2, h);
            h--;
        }
        return count;
    }

    // Function to return the node count for a given subtree
    public static int VSDsubtreeCount(Node current) {
        int leftheight = 0; // variable to hold the height of the left subtree
        int rightheight = 0; // variable to hold the height of the right subtree
        // Traversing to the left subtree to find the max height
        if (current.left != null) {
            leftheight = VSDsubtreeCount(current.left);
        }
        // Traversing to the right subtree to find the max height
        if (current.right != null) {
            rightheight = VSDsubtreeCount(current.right);
        }
        // Selecting the maximum height and adding 1 for root's height
        int count = rightheight + leftheight + 1;
        return count;
    }

    // Function to return the height of the tree
    public static int VSDfindHeight(Node current) {
        if (current == null)
            return -1;
        else {
            int lh = VSDfindHeight(current.left);
            int rh = VSDfindHeight(current.right);

            if (lh > rh)
                return (lh + 1);
            else
                return (rh + 1);
        }
    }

    // Function to display elements in max heap using inorder traversal
    public static void VSDinorder(Node root) {
        if (root.left != null)
            VSDinorder(root.left);
        System.out.println(root.data);
        if (root.right != null)
            VSDinorder(root.right);
    }

    /* Function to choose the most recently inserted element based on count */
    public static void VSDchooseNode(Node current, int level, int size) {
        if (current == null) {
            return;
        }
        if (level == 0) {
            deletecount++;
            if (deletecount == size / 2) {
                parent = current;
            }
            if (deletecount == size) {
                deletenode = current;
                return;
            }
        } else if (level > 0) {

            VSDchooseNode(current.left, level - 1, size);
            VSDchooseNode(current.right, level - 1, size);
        }

    }

    // Function to delete the root node from the heap
    public static Node VSDdeleteNode(Node root, int height, int size) {
        // Obtain the correct child node to replace with the root
        for (int i = 0; i <= height; i++) {
            VSDchooseNode(root, i, size);
        }
        int temp = root.data;
        root.data = deletenode.data;
        deletenode.data = temp;
        // Deleting the node
        if (parent.right != null)
            parent.right = null;
        else
            parent.left = null;
        // calling heapify to maintain max heap properties
        root = VSDHeapify(root);
        return root;
    }

    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);

        System.out.println("Enter the number of elements in the heap:");
        int size = scanner.nextInt();

        int[] arr = new int[size];
        System.out.println("Enter the elements separated by space:");
        for (int i = 0; i < size; i++) {
            arr[i] = scanner.nextInt();
        }

        Node n;
        root = null;
        for (int i = 0; i < arr.length; i++) {
            n = new Node(arr[i]);
            root = VSDbuildHeap(root, n);
            root = VSDHeapify(root); // Calling function to maintain max heap properties
        }

        System.out.println("Insertion");
        VSDinorder(root);

        System.out.println("The descending order is:");
        while (size > 1) {
            deletecount = 0;
            System.out.println(root.data);
            int height = VSDfindHeight(root);
            root = VSDdeleteNode(root, height, size);
            size--;
        }
        System.out.println(root.data);

        scanner.close();
    }
}

step-by-step Explaination:

The VSDMaxHeapSort class contains the main method and other helper methods.
The Node class represents a node in the binary tree. It has three fields: data (holds the value of the node), left (holds the left pointer of the node), and right (holds the right pointer of the node).
The VSDbuildHeap method is used to build the max heap from the given array of integers. It recursively inserts nodes into the tree based on the heap property.
The VSDHeapify method is used to maintain the max heap property by comparing the node with its children and swapping if necessary.
The VSDexpectedCount method calculates the expected number of nodes for a given height in a complete binary tree.
The VSDsubtreeCount method calculates the number of nodes in a subtree rooted at a given node.
The VSDfindHeight method calculates the height of the tree.
The VSDinorder method performs an inorder traversal of the tree and prints the elements in the max heap.
The VSDchooseNode method selects the most recently inserted element based on the count.
The VSDdeleteNode method deletes the root node from the heap and replaces it with the appropriate child node.
The main method creates an array of integers, builds the max heap, and then performs the heap sort by deleting the root node iteratively.

Code(CPP):


/* Copyrights to venkys.io
For more information, visit https://venkys.io */

// Space complexity: O(log n)
// Time complexity: O(n log n)

#include<iostream>
using namespace std;

void swap(int arr[], int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

void printarray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

void VSDmaxheapify(int arr[], int n, int i) {
    int large = i;
    int leftchild = (2 * i) + 1;
    int rightchild = (2 * i) + 2;

    if (leftchild < n && arr[i] < arr[leftchild])
        large = leftchild;
    if (rightchild < n && arr[large] < arr[rightchild])
        large = rightchild;
    if (large != i) {
        swap(arr, i, large);
        VSDmaxheapify(arr, n, large);
    }
}

void VSDminheapify(int arr[], int n, int i) {
    int small = i;
    int leftchild = (2 * i) + 1;
    int rightchild = (2 * i) + 2;

    if (leftchild < n && arr[i] > arr[leftchild]) {
        small = leftchild;
    }
    if (rightchild < n && arr[small] > arr[rightchild]) {
        small = rightchild;
    }
    if (small != i) {
        swap(arr, small, i);
        VSDminheapify(arr, n, small);
    }
}

void VSDMaxheapsort(int arr[], int n) {
    for (int i = (n / 2) - 1; i >= 0; i--) {
        VSDmaxheapify(arr, n, i);
    }
    for (int i = n - 1; i > 0; i--) {
        swap(arr, i, 0);
        VSDmaxheapify(arr, i, 0);
    }
}

void VSDMinheapsort(int arr[], int n) {
    for (int i = (n / 2) - 1; i >= 0; i--) {
        VSDminheapify(arr, n, i);
    }
    for (int i = n - 1; i > 0; i--) {
        swap(arr, i, 0);
        VSDminheapify(arr, i, 0);
    }
}

int main() {
    int n;

    cout << "Enter the number of elements: ";
    cin >> n;

    int arr[n];
    cout << "Enter the elements separated by space: ";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    VSDMaxheapsort(arr, n);
    cout << "Sorted array using max heap sort: ";
    printarray(arr, n);

    VSDMinheapsort(arr, n);
    cout << "Sorted array using min heap sort: ";
    printarray(arr, n);

    return 0;
}

step-by-step Explaination:

The code provided consists of several functions and a main function. Here is a breakdown of the code structure:

swap: This function takes an array and two indices as input and swaps the elements at those indices.
printarray: This function takes an array and its size as input and prints the elements of the array.
VSDmaxheapify: This function takes an array, its size, and an index as input. It performs Max Heapify on the subtree rooted at the given index.
VSDminheapify: This function takes an array, its size, and an index as input. It performs Min Heapify on the subtree rooted at the given index.
VSDMaxheapsort: This function takes an array and its size as input. It builds a Max Heap from the array and performs Heap Sort to sort the array in ascending order.
VSDMinheapsort: This function takes an array and its size as input. It builds a Min Heap from the array and performs Heap Sort to sort the array in descending order.
main: The main function initializes an array with some values, calculates the size of the array, calls the VSDMaxheapsort function to sort the array in ascending order, prints the sorted array, calls the VSDMinheapsort function to sort the array in descending order, and prints the sorted array again.

Time Complexity Analysis:

The time complexity of the MaxHeapSort algorithm is determined by the two main operations: building the max heap and performing heapify during the sorting process.

Building the max heap: The VSDMaxheapsort function calls VSDmaxheapify for each non-leaf node in the heap. The VSDmaxheapify operation has a time complexity of O(log n), where n is the number of elements in the heap. Since there are n/2 non-leaf nodes in a heap, the time complexity of building the max heap is O(n).
Heapify during sorting: The second part of the algorithm involves repeatedly swapping the maximum element with the last element in the array and performing heapify on the remaining elements. This process is repeated n times, where n is the number of elements in the array. The heapify operation has a time complexity of O(log n). Therefore, the time complexity of heapify during sorting is O(n log n).

Overall, the time complexity of the MaxHeapSort algorithm is O(n + n log n), which simplifies to O(n log n) in the worst case.

Space Complexity Analysis:

The space complexity of the MaxHeapSort algorithm is determined by the auxiliary space used during the heapify operation.

Building the max heap: The space complexity of building the max heap is O(1) because it does not require any additional space.
Heapify during sorting: The space complexity of heapify during sorting is O(log n) because it uses the call stack to store the recursive function calls.

Therefore, the overall space complexity of the MaxHeapSort algorithm is O(log n).

It is important to note that the space complexity does not include the space required to store the input and output arrays.

This is the time and space complexity analysis of the MaxHeapSort algorithm.

Real World Applications of MaxHeapSort:

MaxHeapSort, also known as Heap Sort, is a versatile algorithm that finds applications in various domains. Here are some real-world applications where MaxHeapSort is commonly used:

Sorting: The primary application of MaxHeapSort is for sorting elements in an array or a data structure. It efficiently sorts elements in ascending or descending order, making it suitable for applications that require sorting large datasets.
Priority Queues: MaxHeapSort is used to implement priority queues, where elements with higher priority are dequeued first. The heap data structure, based on MaxHeapSort, efficiently supports insertion, deletion, and retrieval operations in priority queues.
Operating Systems: MaxHeapSort is utilized in operating systems for scheduling processes based on priority levels. It helps determine the order in which processes should be executed, allowing for efficient resource allocation and management.
Graph Algorithms: MaxHeapSort plays a crucial role in various graph algorithms, such as Dijkstra's algorithm for finding the shortest path in a graph. It assists in selecting the next vertex with the highest priority during graph traversal.
Event Scheduling: MaxHeapSort is employed in event-driven systems, where events have different priorities based on their significance or urgency. It ensures that events are processed in the correct order based on their priority levels.
Simulation and Gaming: MaxHeapSort is useful in simulation and gaming scenarios, such as real-time strategy games or simulations that require efficient sorting of game entities or events based on their priorities.

These are just a few examples of the real-world applications of MaxHeapSort. The algorithm's ability to efficiently handle priority-based operations and sort data makes it a valuable tool in various domains.