Implement Max Heap

Heaps Theory and Implementation Medium

You need to implement the Min Heap with the following given methods.

insert (x) -> insert value x to the max heap
getMax -> Output the maximum value from the max heap
exctractMax -> Remove the maximum element from the heap
heapSize -> return the current size of the heap
isEmpty -> returns if heap is empty or not
changeKey (ind, val) -> update the value at given index to val (index will be given 0-based indexing)
initializeHeap -> Initialize the heap

Constraints

1 <= n <= 105
-105 <= nums[i] <= 105

Hints

"Since the maximum value is the largest number stored, it must be found by scanning the heap (worst case O(n)). Alternatively, maintain a secondary max pointer while inserting elements (if extra space is allowed)."
"Find the largest value in the heap (brute-force O(n) scan). Swap it with the last element, remove it, and heapify down to restore the min-heap order."

Company Tags

Boston Consulting Group Airbnb McKinsey & Company Rockstar Games Splunk Swiggy Western Digital Roche Byju's MongoDB Ernst & Young Reddit Visa Chewy Unity Technologies JPMorgan Chase Zomato Nutanix Optum Walmart Goldman Sachs PayPal Cloudflare Flipkart Cerner Google Microsoft Amazon Meta Apple Netflix Adobe

Editorial

              document.body.innerHTML = '';
              const iframeHTML = `
                <div style="padding-top:56.25%;position:relative;">
                  <iframe 
                    src="https://app.tpstreams.com/embed/atsjxr/66hfqHRSajU/?access_token=33e345b1-9f22-4382-8c5c-7e49a75d8027" 
                    style="border:0;max-width:100%;position:absolute;top:0;left:0;height:100%;width:100%;" 
                    allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" 
                    allowfullscreen="" 
                    frameborder="0">
                  </iframe>
                </div>
              `;
              document.body.innerHTML = iframeHTML;
              
              const script = document.createElement('script');
              script.src = 'https://static.testpress.in/static/js/player.js';
              document.head.appendChild(script);
              
              script.onload = () => {
                const iframe = document.querySelector('iframe');
                const player = new Testpress.Player(iframe);
              
                player.loaded().then(() => {
                  console.log('Player is ready now');
                });
              
                player.on('play', () => {
                  console.log('Played the video');
                });
              };

Pre-requisites: Heap theory, Heapify Algorithm

Approach:

The goal is to implement a maximum heap data structure that will provide different operations to the user. The idea to use a list/array to store the elements in an order that follows the max-heap property. An array stores a complete binary tree without using extra pointers for child links. It allows calculating parent and child positions with simple index arithmetic and keeps all elements close together for faster memory access, making it both space-efficient and quick to update or reorder elements. Here's how different function can be implemented:

1. Insert(val):

The element can be added at the back of the list. Since, this element may not follow the max-heap property, it can be heapified upwards.

2. Get Maximum():

The maximum value will always be stored at the 0th index as the array follows the max-heap property.

3. Extract Maximum():

If the largest value (located at 0th index) is removed directly, all the elements in the array will need to be shifted by one index making it a costly operation. Instead, the largest value can be swapped with the element at last index. The value at the last index (currently storing the largest value) can be popped out from the back of the array/list.

Since, the element at the 0th index does not follow the max-heap property (because it was swapped), it must be heapified downwards.

4. Heap Size():

The size of the array/list can be returned directly as the heap size.

5. Is Empty():

If the array size is zero, the heap can be marked as empty.

6. Change Key(ind, val):

The value at particular index can be easily updated in the list. This updated value might disturb the max-heap property of the array, so it needs to be heapified upwards or downwards accordingly.

Solution:

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    vector<int> arr; // list to store the max-heap
    int count; // to store the count of elements in max-heap
    
    // Function to recursively heapify the array upwards
    void heapifyUp(int ind) {
        int parentInd = (ind - 1)/2; 

        // If current index holds larger value than the parent
        if(ind > 0 && arr[ind] > arr[parentInd]) {
            // Swap the values at the two indices
            swap(arr[ind], arr[parentInd]);
            
            // Recursively heapify the upper nodes
            heapifyUp(parentInd);
        } 

        return;
    }
    
    // Function to recursively heapify the array downwards
    void heapifyDown(int ind) {
        int n = arr.size(); // Size of the array

        // To store the index of largest element
        int largestInd = ind; 

        // Indices of the left and right children
        int leftChildInd = 2*ind + 1, rightChildInd = 2*ind + 2;
        
        // If the left child holds larger value, update the largest index
        if(leftChildInd < n && arr[leftChildInd] > arr[largestInd]) 
            largestInd = leftChildInd;

        // If the right child holds larger value, update the largest index
        if(rightChildInd < n && arr[rightChildInd] > arr[largestInd]) 
            largestInd = rightChildInd;

        // If the largest element index is updated
        if(largestInd != ind) {
            // Swap the largest element with the current index
            swap(arr[largestInd] , arr[ind]);

            // Recursively heapify the lower subtree
            heapifyDown(largestInd);
        }

        return; 
    }
    
public:
    // Method to intialize the max-heap data structure
    void initializeHeap(){
        arr.clear();
        count = 0;
    }
    
    // Method to insert a given value in the max-heap
    void insert(int key){
        // Insert the value at the back of the list 
        arr.push_back(key);
        
        // Heapify upwards
        heapifyUp(count);
        count = count+1; // Increment the counter;
        
        return;
    }
        
    // Method to change the value at a given index in max-heap
    void changeKey(int index, int new_val){
        // If the current value is replaced with a larger value
        if(arr[index] < new_val) {
            arr[index] = new_val;
            heapifyUp(index);
        }

        // Otherwise (if the current value is replaced with smaller value)
        else {
            arr[index] = new_val;
            heapifyDown(index);
        }

        return;
    }
    
    // Method to extract the maximum value from the max-heap
    void extractMax(){
        int ele = arr[0]; // maximum value in the heap
        
        // Swap the top value with the value at last index
        swap(arr[0], arr[count-1]); 
        
        arr.pop_back(); // Pop the maximum value from the list
        count = count - 1; // Decrement the counter
        
        // Heapify the root value downwards
        heapifyDown(0);
    }
    
    // Method to return if the max-heap is empty
    bool isEmpty(){
        return (count == 0);
    }
    
    // Method to return the maximum value in the max-heap
    int getMax(){
        // Return the value stored at the root
        return arr[0];
    }
    
    // Method to return the size of max-heap
    int heapSize(){
        return count;
    }
};

// Driver code
int main() {
    // Creating an object of the Solution class
    Solution heap;

    // Initializing a max heap data structure 
    heap.initializeHeap();
    
    // Performing different operations
    heap.insert(4); cout << "Inserting 4 in the max-heap\n";
    heap.insert(1); cout << "Inserting 1 in the max-heap\n";
    heap.insert(10); cout << "Inserting 10 in the max-heap\n";
    cout << "Maximum value in the heap is: " << heap.getMax() << "\n";
    cout << "Size of max-heap is: " << heap.heapSize() << "\n";
    cout << "Is heap empty: " << heap.isEmpty() << "\n";
    cout << "Extracting maximum value from the heap\n"; heap.extractMax();
    cout << "Changing value at index 0 to 16\n"; heap.changeKey(0, 16);
    cout << "Maximum value in the heap is: " << heap.getMax();
    
    return 0;
}
import java.util.*;

class Solution {
    private List<Integer> arr; // list to store the max-heap
    private int count; // to store the count of elements in max-heap
    
    // Constructor
    public Solution() {
        arr = new ArrayList<>();
        count = 0;
    }
    
    // Function to recursively heapify the array upwards
    private void heapifyUp(int ind) {
        int parentInd = (ind - 1)/2; 

        // If current index holds larger value than the parent
        if(ind > 0 && arr.get(ind) > arr.get(parentInd)) {
            // Swap the values at the two indices
            int temp = arr.get(ind);
            arr.set(ind, arr.get(parentInd));
            arr.set(parentInd, temp);
            
            // Recursively heapify the upper nodes
            heapifyUp(parentInd);
        } 

        return;
    }
    
    // Function to recursively heapify the array downwards
    private void heapifyDown(int ind) {
        int n = arr.size(); // Size of the array

        // To store the index of largest element
        int largestInd = ind; 

        // Indices of the left and right children
        int leftChildInd = 2*ind + 1;
        int rightChildInd = 2*ind + 2;
        
        // If the left child holds larger value, update the largest index
        if(leftChildInd < n && arr.get(leftChildInd) > arr.get(largestInd)) 
            largestInd = leftChildInd;

        // If the right child holds larger value, update the largest index
        if(rightChildInd < n && arr.get(rightChildInd) > arr.get(largestInd)) 
            largestInd = rightChildInd;

        // If the largest element index is updated
        if(largestInd != ind) {
            // Swap the largest element with the current index
            int temp = arr.get(largestInd);
            arr.set(largestInd, arr.get(ind));
            arr.set(ind, temp);

            // Recursively heapify the lower subtree
            heapifyDown(largestInd);
        }

        return; 
    }
    
    // Method to intialize the max-heap data structure
    public void initializeHeap(){
        arr.clear();
        count = 0;
    }
    
    // Method to insert a given value in the max-heap
    public void insert(int key){
        // Insert the value at the back of the list 
        arr.add(key);
        
        // Heapify upwards
        heapifyUp(count);
        count = count + 1; // Increment the counter;
        
        return;
    }
        
    // Method to change the value at a given index in max-heap
    public void changeKey(int index, int new_val){
        // If the current value is replaced with a larger value
        if(arr.get(index) < new_val) {
            arr.set(index, new_val);
            heapifyUp(index);
        }
        // Otherwise (if the current value is replaced with smaller value)
        else {
            arr.set(index, new_val);
            heapifyDown(index);
        }

        return;
    }
    
    // Method to extract the maximum value from the max-heap
    public void extractMax(){
        int ele = arr.get(0); // maximum value in the heap
        
        // Swap the top value with the value at last index
        int temp = arr.get(count - 1);
        arr.set(count - 1, arr.get(0));
        arr.set(0, temp);
        
        arr.remove(count - 1); // Pop the maximum value from the list
        count = count - 1; // Decrement the counter
        
        // Heapify the root value downwards
        if(count > 0) {
            heapifyDown(0);
        }
    }
    
    // Method to return if the max-heap is empty
    public boolean isEmpty(){
        return (count == 0);
    }
    
    // Method to return the maximum value in the max-heap
    public int getMax(){
        // Return the value stored at the root
        return arr.get(0);
    }
    
    // Method to return the size of max-heap
    public int heapSize(){
        return count;
    }
}

class Main {
    public static void main(String[] args) {
        // Creating an object of the Solution class
        Solution heap = new Solution();

        // Initializing a max heap data structure 
        heap.initializeHeap();
        
        // Performing different operations
        heap.insert(4); System.out.println("Inserting 4 in the max-heap");
        heap.insert(1); System.out.println("Inserting 1 in the max-heap");
        heap.insert(10); System.out.println("Inserting 10 in the max-heap");
        System.out.println("Maximum value in the heap is: " + heap.getMax());
        System.out.println("Size of max-heap is: " + heap.heapSize());
        System.out.println("Is heap empty: " + heap.isEmpty());
        System.out.println("Extracting maximum value from the heap");
        heap.extractMax();
        System.out.println("Changing value at index 0 to 16");
        heap.changeKey(0, 16);
        System.out.println("Maximum value in the heap is: " + heap.getMax());
    }
}
class Solution:
    def __init__(self):
        self.arr = []  # list to store the max-heap
        self.count = 0  # to store the count of elements in max-heap

    # Function to recursively heapify the array upwards
    def heapifyUp(self, ind):
        parentInd = (ind - 1)//2

        # If current index holds larger value than the parent
        if ind > 0 and self.arr[ind] > self.arr[parentInd]:
            # Swap the values at the two indices
            self.arr[ind], self.arr[parentInd] = self.arr[parentInd], self.arr[ind]
            
            # Recursively heapify the upper nodes
            self.heapifyUp(parentInd)
        return

    # Function to recursively heapify the array downwards
    def heapifyDown(self, ind):
        n = len(self.arr)  # Size of the array

        # To store the index of largest element
        largestInd = ind

        # Indices of the left and right children
        leftChildInd = 2*ind + 1
        rightChildInd = 2*ind + 2
        
        # If the left child holds larger value, update the largest index
        if leftChildInd < n and self.arr[leftChildInd] > self.arr[largestInd]:
            largestInd = leftChildInd

        # If the right child holds larger value, update the largest index
        if rightChildInd < n and self.arr[rightChildInd] > self.arr[largestInd]:
            largestInd = rightChildInd

        # If the largest element index is updated
        if largestInd != ind:
            # Swap the largest element with the current index
            self.arr[largestInd], self.arr[ind] = self.arr[ind], self.arr[largestInd]

            # Recursively heapify the lower subtree
            self.heapifyDown(largestInd)
        return

    # Method to intialize the max-heap data structure
    def initializeHeap(self):
        self.arr.clear()
        self.count = 0

    # Method to insert a given value in the max-heap
    def insert(self, key):
        # Insert the value at the back of the list
        self.arr.append(key)
        
        # Heapify upwards
        self.heapifyUp(self.count)
        self.count += 1  # Increment the counter
        return

    # Method to change the value at a given index in max-heap
    def changeKey(self, index, new_val):
        # If the current value is replaced with a larger value
        if self.arr[index] < new_val:
            self.arr[index] = new_val
            self.heapifyUp(index)
        # Otherwise (if the current value is replaced with smaller value)
        else:
            self.arr[index] = new_val
            self.heapifyDown(index)
        return

    # Method to extract the maximum value from the max-heap
    def extractMax(self):
        ele = self.arr[0]  # maximum value in the heap

        # Swap the top value with the value at last index
        self.arr[0], self.arr[self.count - 1] = self.arr[self.count - 1], self.arr[0]

        # Pop the maximum value from the list
        self.arr.pop()
        self.count -= 1  # Decrement the counter

        # Heapify the root value downwards
        if self.count > 0:
            self.heapifyDown(0)

    # Method to return if the max-heap is empty
    def isEmpty(self):
        return (self.count == 0)

    # Method to return the maximum value in the max-heap
    def getMax(self):
        # Return the value stored at the root
        return self.arr[0]

    # Method to return the size of max-heap
    def heapSize(self):
        return self.count


# Driver code
def main():
    # Creating an object of the Solution class
    heap = Solution()

    # Initializing a max heap data structure
    heap.initializeHeap()
    
    # Performing different operations
    heap.insert(4); print("Inserting 4 in the max-heap")
    heap.insert(1); print("Inserting 1 in the max-heap")
    heap.insert(10); print("Inserting 10 in the max-heap")
    print("Maximum value in the heap is:", heap.getMax())
    print("Size of max-heap is:", heap.heapSize())
    print("Is heap empty:", heap.isEmpty())
    print("Extracting maximum value from the heap")
    heap.extractMax()
    print("Changing value at index 0 to 16")
    heap.changeKey(0, 16)
    print("Maximum value in the heap is:", heap.getMax())

if __name__ == "__main__":
    main()
    
class Solution {
    constructor() {
        this.arr = []; // list to store the max-heap
        this.count = 0; // to store the count of elements in max-heap
    }
    
    // Function to recursively heapify the array upwards
    heapifyUp(ind) {
        let parentInd = Math.floor((ind - 1) / 2);

        // If current index holds larger value than the parent
        if(ind > 0 && this.arr[ind] > this.arr[parentInd]) {
            // Swap the values at the two indices
            [this.arr[ind], this.arr[parentInd]] = [this.arr[parentInd], this.arr[ind]];
            
            // Recursively heapify the upper nodes
            this.heapifyUp(parentInd);
        }
        return;
    }
    
    // Function to recursively heapify the array downwards
    heapifyDown(ind) {
        let n = this.arr.length; // Size of the array

        // To store the index of largest element
        let largestInd = ind; 

        // Indices of the left and right children
        let leftChildInd = 2 * ind + 1;
        let rightChildInd = 2 * ind + 2;
        
        // If the left child holds larger value, update the largest index
        if(leftChildInd < n && this.arr[leftChildInd] > this.arr[largestInd]) {
            largestInd = leftChildInd;
        }

        // If the right child holds larger value, update the largest index
        if(rightChildInd < n && this.arr[rightChildInd] > this.arr[largestInd]) {
            largestInd = rightChildInd;
        }

        // If the largest element index is updated
        if(largestInd !== ind) {
            // Swap the largest element with the current index
            [this.arr[largestInd], this.arr[ind]] = [this.arr[ind], this.arr[largestInd]];
            
            // Recursively heapify the lower subtree
            this.heapifyDown(largestInd);
        }
        return;
    }
    
    // Method to intialize the max-heap data structure
    initializeHeap() {
        this.arr = [];
        this.count = 0;
    }
    
    // Method to insert a given value in the max-heap
    insert(key) {
        // Insert the value at the back of the list 
        this.arr.push(key);
        
        // Heapify upwards
        this.heapifyUp(this.count);
        this.count = this.count + 1; // Increment the counter;
        
        return;
    }
        
    // Method to change the value at a given index in max-heap
    changeKey(index, new_val) {
        // If the current value is replaced with a larger value
        if(this.arr[index] < new_val) {
            this.arr[index] = new_val;
            this.heapifyUp(index);
        }
        // Otherwise (if the current value is replaced with smaller value)
        else {
            this.arr[index] = new_val;
            this.heapifyDown(index);
        }
        return;
    }
    
    // Method to extract the maximum value from the max-heap
    extractMax() {
        let ele = this.arr[0]; // maximum value in the heap
        
        // Swap the top value with the value at last index
        [this.arr[0], this.arr[this.count - 1]] = [this.arr[this.count - 1], this.arr[0]];
        
        this.arr.pop(); // Pop the maximum value from the list
        this.count = this.count - 1; // Decrement the counter
        
        // Heapify the root value downwards
        if(this.count > 0) {
            this.heapifyDown(0);
        }
    }
    
    // Method to return if the max-heap is empty
    isEmpty() {
        return (this.count === 0);
    }
    
    // Method to return the maximum value in the max-heap
    getMax() {
        // Return the value stored at the root
        return this.arr[0];
    }
    
    // Method to return the size of max-heap
    heapSize() {
        return this.count;
    }
}

// Driver code
function main() {
    // Creating an object of the Solution class
    let heap = new Solution();

    // Initializing a max heap data structure 
    heap.initializeHeap();
    
    // Performing different operations
    heap.insert(4); console.log("Inserting 4 in the max-heap");
    heap.insert(1); console.log("Inserting 1 in the max-heap");
    heap.insert(10); console.log("Inserting 10 in the max-heap");
    console.log("Maximum value in the heap is: " + heap.getMax());
    console.log("Size of max-heap is: " + heap.heapSize());
    console.log("Is heap empty: " + heap.isEmpty());
    console.log("Extracting maximum value from the heap");
    heap.extractMax();
    console.log("Changing value at index 0 to 16");
    heap.changeKey(0, 16);
    console.log("Maximum value in the heap is: " + heap.getMax());
}

// Run the driver code
main();

Complexity Analysis:

Considering there are maximum N elements inserted in the heap data structure,

Time Complexity:

Insert(val): Inserting and Heapifying upwards contribute to O(logN) time.
Get Maximum(): Constant time operation, i.e., O(1).
Extract Maximum(): Involves Heapifying downwards contributing to O(logN) time.
Heap Size(): Constant time operation, i.e., O(1).
Is Empty(): Constant time operation, i.e., O(1).
Change Key(ind, val): Involves heapifying which takes O(logN) time.

Space Complexity: O(N), because of the array used to store the elements.

Code

Problem List