Search⌘ K
AI Features
Home
Courses
Data Structures for Coding Interviews in C#

Max Heap (Implementation)

Learn how to implement a max heap in C# by building essential functions such as getMax, insert, removeMax, percolateUp, and maxHeapify. Understand their time complexities and how to build a max heap efficiently using bottom-up heapify to optimize your coding interview skills.

We'll cover the following...

Max heap Implementation

Start with some function declarations for the heap class.

C#
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

C#
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()

C#
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!

C#
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 ...