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, ...