Data Structures for Coding Interviews in C#/

...

/

Max Heap (Implementation)

Max Heap (Implementation)

Implement a max heap!

We'll cover the following...

Max heap Implementation

Start with some function declarations for the heap class.

Press + to interact
main.cs
MaxHeap.cs
using System;



namespace chapter_8

{

    class MaxHeap<T>

    {

        

        void percolateUp(int i) { }

        void maxHeapify(int i) { }





        public MaxHeap() { }

        public int size() {

            return 0;

        }

        public T getMax() 

        {

            return (T)Convert.ChangeType(-1, typeof(T));

        }

        public void insert(T  key) {}

        public void removeMax() { }

        public void buildHeap(T [] arr, int size)

        {



        }

    }

}

Structure of our MaxHeap #

Declaring the private elements #

Press + to interact
main.cs
MaxHeap.cs
using System;



namespace chapter_8

{

    class MaxHeap<T>

    {

        

        void percolateUp(int i) { }

        void maxHeapify(int i) { }

        public MaxHeap() { }

        public int size() {

            return 0;

        }

        public T getMax() 

        {

            return (T)Convert.ChangeType(-1, typeof(T));

        }

        public void insert(T  key) {}

        public void removeMax() { }

        public void buildHeap(T [] arr, int size)

        {



        }   

        public int parent(int i)

        {

            return (i - 1) / 2;

        }

        public int lchild(int i)

        {

            return i * 2 + 1;

        }

        public int rchild(int i)

        {

            return i * 2 + 2;

        }

    }

}

Implementing the constructor and size() #

Press + to interact
main.cs
MaxHeap.cs
using System;

using System.Collections.Generic;



namespace chapter_8

{

    class MaxHeap<T>

    {

        

        void percolateUp(int i) { }

        void maxHeapify(int i) { }



        List<T> h = null;

        public MaxHeap() {

            h = new List<T>();

        }

        public int size() {

            return h.Count;

        }

        public T getMax() 

        {

            return (T)Convert.ChangeType(-1, typeof(T));

        }

        public void insert(T  key) {}

        public void removeMax() { }

        public void buildHeap(T [] arr, int size)

        {



        }   

        public int parent(int i)

        {

            return (i - 1) / 2;

        }

        public int lchild(int i)

        {

            return i * 2 + 1;

        }

        public int rchild(int i)

        {

            return i * 2 + 2;

        }

    }

}

Implementing the getMax() function

This function returns the maximum value from the heap, which is the root, i.e., the first value in the list. It does not modify the heap itself. If the heap is empty, then this function returns -1. The time complexity of this function is in O(1)O(1) constant time, which is what makes heaps so special!

Press + to interact
main.cs
MaxHeap.cs
using System;

using System.Collections.Generic;



namespace chapter_8

{

    class MaxHeap<T>

    {

        

        void percolateUp(int i) { }

        void maxHeapify(int i) { }



        List<T> h = null;

        public MaxHeap() {

            h = new List<T>();

        }

        public int size() {

            return h.Count;

        }

        public T getMax() 

        {

            if (size() <= 0)

            {

                return (T)Convert.ChangeType(-1, typeof(T));

            }

            else

                return h[0];

            

        }

        public void insert(T  key) {}

        public void removeMax() { }

        public void buildHeap(T [] arr, int size)

        {



        }   

        public int parent(int i)

        {

            return (i - 1) / 2;

        }

        public int lchild(int i)

        {

            return i * 2 + 1;

        }

        public int rchild(int i)

        {

            return i * 2 + 2;

        }

    }

}

Implementing the removeMax() function

This function removes the maximum value from the heap. It first checks if the length of the heap is 1. If true, it deletes the value at index 0. Then, it checks if the length of the heap is greater than 1. If it is, it swaps the maximum value with the last leaf node, deletes it, and restores the max heap property on the rest of the tree by calling the maxHeapify() function on it. The time complexity of this function is in O(log(n))O(log(n)) because that is the maximum number of nodes that would have to be traversed or swapped.

Press + to interact
main.cs
MaxHeap.cs
using System;

using System.Collections.Generic;



namespace chapter_8

{

    class MaxHeap<T>

    {

        

        void percolateUp(int i) { }

        void maxHeapify(int i) { }



        List<T> h = null;

        public MaxHeap() {

            h = new List<T>();

        }

        public int size() {

            return h.Count;

        }

        public T getMax() 

        {

            if (size() <= 0)

            {

                return (T)Convert.ChangeType(-1, typeof(T));

            }

            else

                return h[0];

            

        }

        public void insert(T  key) {}

        public void buildHeap(T [] arr, int size)

        {



        }   

        public int parent(int i)

        {

            return (i - 1) / 2;

        }

        public int lchild(int i)

        {

            return i * 2 + 1;

        }

        public int rchild(int i)

        {

            return i * 2 + 2;

        }

        public void removeMax()

        {

            if (size() == 1)

            {

                // Remove the last item from the list

                h.RemoveAt(h.Count - 1);

            }

            else if (size() > 1)

            {

                // Built-in function in STL which swaps the value of two variables

                T temp = h[0];

                h[0] = h[size() - 1];

                h[size() - 1] = temp;

                // Deletes the last element

                h.RemoveAt(h.Count - 1);

                // Restore heap property

                maxHeapify(0);

            }

            

        }

    }

}

Implementing the insert() function

This function appends the given value to the heap list and calls the percolateUp() function on it. This function will keep on swapping the values of nodes until the heap property is restored. The time complexity of this function is in O(log(n))O(log(n)) because that is the maximum number of nodes that would have to be traversed or swapped.

Press + to interact
main.cs
MaxHeap.cs
using System;

using System.Collections.Generic;



namespace chapter_8

{

    class MaxHeap<T>

    {

        

        void percolateUp(int i) { }

        void maxHeapify(int i) { }



        List<T> h = null;

        public MaxHeap() {

            h = new List<T>();

        }

        public int size() {

            return h.Count;

        }

        public T getMax() 

        {

            if (size() <= 0)

            {

                return (T)Convert.ChangeType(-1, typeof(T));

            }

            else

                return h[0];

            

        }

        public void insert(T  key) 

        {

            // Push elements into vector from the back

            h.RemoveAt(h.Count - 1);

            // Store index of last value of vector in variable i

            int i = size() - 1;

            // Restore heap property

            percolateUp(i);

        }

        public void buildHeap(T [] arr, int size)

        {



        }   

        public int parent(int i)

        {

            return (i - 1) / 2;

        }

        public int lchild(int i)

        {

            return i * 2 + 1;

        }

        public int rchild(int i)

        {

            return i * 2 + 2;

        }

        public void removeMax()

        {

            if (size() == 1)

            {

                // Remove the last item from the list

                h.RemoveAt(h.Count - 1);

            }

            else if (size() > 1)

            {

                // Swaps the value of two variables

                T temp = h[0];

                h[0] = h[size() - 1];

                h[size() - 1] = temp;

                // Deletes the last element

                h.RemoveAt(h.Count - 1);

                // Restore heap property

                maxHeapify(0);

            }

            

        }

    }

}

Implementing the percolateUp() function

This function restores the heap property by swapping the value at a parent node if it is less than the value at a child node. After swapping, the function is called recursively on each parent node until the root is reached. The time complexity of this function is in O(log(n))O(log(n)) because that is the maximum number of nodes that would have to be traversed and/or swapped.

Press + to interact
main.cs
MaxHeap.cs
using System;

using System.Collections.Generic;



namespace chapter_8

{

    class MaxHeap<T> where T: IComparable<T>

    {



        void percolateUp(int i)

        {

            if (i <= 0)

                return;

            else if (h[parent(i)].CompareTo ( h[i]) < 0)

            {

                // Swaps the value of two variables

                T temp = h[i];

                h[i] = h[parent(i)];

                h[size() - 1] = temp;

                percolateUp(parent(i));

            }

        }

        void maxHeapify(int i) { }



        List<T> h = null;

        public MaxHeap() {

            h = new List<T>();

        }

        public int size() {

            return h.Count;

        }

        public T getMax() 

        {

            if (size() <= 0)

            {

                return (T)Convert.ChangeType(-1, typeof(T));

            }

            else

                return h[0];           

        }

        public void insert(T  key) 

        {

            // Push elements into vector from the back

            h.RemoveAt(h.Count - 1);

            // Store index of last value of vector in  variable i

            int i = size() - 1;

            // Restore heap property

            percolateUp(i);

        }

        public void buildHeap(T [] arr, int size)

        {



        }   

        public int parent(int i)

        {

            return (i - 1) / 2;

        }

        public int lchild(int i)

        {

            return i * 2 + 1;

        }

        public int rchild(int i)

        {

            return i * 2 + 2;

        }

        public void removeMax()

        {

            if (size() == 1)

            {

                // Remove the last item from the list

                h.RemoveAt(h.Count - 1);

            }

            else if (size() > 1)

            {

                // Swaps the value of two variables

                T temp = h[0];

                h[0] = h[size() - 1];

                h[size() - 1] = temp;

                // Deletes the last element

                h.RemoveAt(h.Count - 1);

                // Restore heap property

                maxHeapify(0);

            }

            

        }



    }

}

Implementing the maxHeapify() function

The maxHeapify() function restores the heap property after a node is removed. It restores the heap property by starting from a given node and continuing down to the leaves. It swaps the values of the parent nodes with the values of their largest child nodes until the heap property is restored. The time complexity of this function is in O(log(n))O(log(n)) because that is the maximum number of nodes that would have to be traversed or swapped.

Press + to interact
main.cs
MaxHeap.cs
using System;

using System.Collections.Generic;



namespace chapter_8

{

    class MaxHeap<T> where T: IComparable<T>

    {



        void percolateUp(int i)

        {

            if (i <= 0)

                return;

            else if (h[parent(i)].CompareTo ( h[i]) < 0)

            {

                // Swaps the value of two variables

                T temp = h[i];

                h[i] = h[parent(i)];

                h[size() - 1] = temp;

                percolateUp(parent(i));

            }

        }

        public void maxHeapify(int i) 

        {

            int lc = lchild(i);

            int rc = rchild(i);

            int imax = i;



            if (lc < size() && (h[lc].CompareTo(h[imax]) > 0))

                imax = lc;

            if (rc < size() && (h[rc].CompareTo(h[imax]) > 0))

                imax = rc;

            if (i != imax)

            {

                T temp = h[i];

                h[i] = h[imax];

                h[imax] = temp;

                maxHeapify(imax);

            }

        }



        List<T> h = null;

        public MaxHeap() {

            h = new List<T>();

        }

        public int size() {

            return h.Count;

        }

        public T getMax() 

        {

            if (size() <= 0)

            {

                return (T)Convert.ChangeType(-1, typeof(T));

            }

            else

                return h[0];           

        }

        public void insert(T  key) 

        {

            // Push elements into vector from the back

            h.RemoveAt(h.Count - 1);

            // Store index of last value of vector in  variable i

            int i = size() - 1;

            // Restore heap property

            percolateUp(i);

        }

        public void buildHeap(T [] arr, int size)

        {



        }   

        public int parent(int i)

        {

            return (i - 1) / 2;

        }

        public int lchild(int i)

        {

            return i * 2 + 1;

        }

        public int rchild(int i)

        {

            return i * 2 + 2;

        }

        public void removeMax()

        {

            if (size() == 1)

            {

                // Remove the last item from the list

                h.RemoveAt(h.Count - 1);

            }

            else if (size() > 1)

            {

                // Swaps the value of two variables

                T temp = h[0];

                h[0] = h[size() - 1];

                h[size() - 1] = temp;

                // Deletes the last element

                h.RemoveAt(h.Count - 1);

                // Restore heap property

                maxHeapify(0);

            }

            

        }



    }

}

Building a max-heap

Build a max heap now! Suppose you have nn elements in an array, which represents your heap. For every node to be positioned in accordance with the max heap property, call the maxHeapify method at every index of that array starting from the bottom of the heap (lines 74-82).

Press + to interact
main.cs
MaxHeap.cs
using System;

using System.Collections.Generic;



namespace chapter_8

{

    class MaxHeap<T> where T: IComparable<T>

    {



        void percolateUp(int i)

        {

            if (i <= 0)

                return;

            else if (h[parent(i)].CompareTo ( h[i]) < 0)

            {

                // Swaps the value of two variables

                T temp = h[i];

                h[i] = h[parent(i)];

                h[parent(i)] = temp;

                percolateUp(parent(i));

            }

        }

        public void maxHeapify(int i) 

        {

            int lc = lchild(i);

            int rc = rchild(i);

            int imax = i;



            if (lc < size() && (h[lc].CompareTo(h[imax]) > 0))

                imax = lc;

            if (rc < size() && (h[rc].CompareTo(h[imax]) > 0))

                imax = rc;

            if (i != imax)

            {

                T temp = h[i];

                h[i] = h[imax];

                h[imax] = temp;

                maxHeapify(imax);

            }

        }



        List<T> h = null;

        public MaxHeap() {

            h = new List<T>();

        }

        public int size() {

            return h.Count;

        }

        public T getMax() 

        {

            if (size() <= 0)

            {

                return (T)Convert.ChangeType(-1, typeof(T));

            }

            else

                return h[0];           

        }

        public void insert(T  key) 

        {

            // Push elements into vector from the back

            h.Add(key);

            // Store index of last value of vector in  variable i

            int i = size() - 1;

            // Restore heap property

            percolateUp(i);

        }

        public void printHeap()

        {

            for (int i = 0; i <= size() - 1; i++)

            {

                Console.Write( h[i] + " ") ;

            }

            Console.WriteLine("");

        }

        public void buildHeap(T [] arr, int size)

        {

            // Copy elements of array into the List h 

            h.AddRange(arr);

            for (int i = (size - 1) / 2; i >= 0; i--)

            {

                maxHeapify(i);

            }

        }   

        public int parent(int i)

        {

            return (i - 1) / 2;

        }

        public int lchild(int i)

        {

            return i * 2 + 1;

        }

        public int rchild(int i)

        {

            return i * 2 + 2;

        }

        public void removeMax()

        {

            if (size() == 1)

            {

                // Remove the last item from the list

                h.RemoveAt(h.Count - 1);

            }

            else if (size() > 1)

            {

                // Swaps the value of two variables

                T temp = h[0];

                h[0] = h[size() - 1];

                h[size() - 1] = temp;

                // Deletes the last element

                h.RemoveAt(h.Count - 1);

                // Restore heap property

                maxHeapify(0);

            }

            

        }



    }

}

Derive a tight bound for the complexity of ...