# My Solution Along with Implementation of MaxHeap<T> and MinHeap<T> in C#

• ``````public class MedianFinder
{
MinHeap<int> minheap;
MaxHeap<int> maxheap;

/** initialize your data structure here. */
public MedianFinder()
{
minheap = new MinHeap<int>();
maxheap = new MaxHeap<int>(); ;
}

public void AddNum(int num) //Always trying to keep maxheap.Count>=minheap.Count
{
if (maxheap.Count == 0) maxheap.Insert(num);
else if(maxheap.Count>minheap.Count)
{
if(num>=maxheap.Max) //it belongs to minheap, and there is enough space
{
minheap.Insert(num);
}
else //it belongs to maxheap, but there is no enough space
{
minheap.Insert(maxheap.ExtractMax());
maxheap.Insert(num);
}
}
else if (maxheap.Count==minheap.Count)
{
if (num >= maxheap.Max) //it belongs to minheap, but there is no enough space
{
maxheap.Insert(minheap.ExtractMin());
minheap.Insert(num);
}
else //it belongs to maxheap and there is enough space
{
maxheap.Insert(num);
}
}

}

public double FindMedian()
{
int count = minheap.Count + maxheap.Count;
if (count % 2 == 0) //if even, average of two middle ones
{
return Convert.ToDouble(minheap.Min + maxheap.Max) / 2;
}
else
return maxheap.Max;
}
}

class MaxHeap<T> where T:IComparable<T>
{
private List<T> Heap;

public MaxHeap()
{
Heap = new List<T>();
}

public T Max
{
get
{
if (Heap.Count == 0) throw new NullReferenceException();
else return Heap[0];
}
}
public bool IsEmpty()
{
return Heap == null || Heap.Count == 0;
}

public int Count
{
get
{
if (Heap == null) return 0;
else
{
return Heap.Count;
}
}
}

public void Insert(T data)
{

int ch = Heap.Count - 1; //ch for child
while (ch > 0)
{
int p = (ch - 1) / 2; //p for parent

if (Heap[ch].CompareTo(Heap[p]) > 0) //meaning child is bigger than parent -> Swap'm
{
Swap(p, ch);
ch = p;
}
else
break;
}
}

private void Swap(int p, int ch)
{
T temp = Heap[p];
Heap[p] = Heap[ch];
Heap[ch] = temp;
}

public T ExtractMax()
{
if (Heap == null || Heap.Count == 0) throw new NullReferenceException();
T ret = Heap[0];

Heap[0] = Heap[Heap.Count - 1];
Heap.RemoveAt(Heap.Count - 1);

Heapify(0);

return ret;
}
private void Heapify(int i) //i is parent
{
int ch1 = 2 * i + 1; //left child
int ch2 = 2 * i + 2; // right child

if (ch1 >= Heap.Count && ch2 >= Heap.Count) return;

int bigger = (ch2 >= Heap.Count) ? ch1 : (Heap[ch1].CompareTo(Heap[ch2]) > 0) ? ch1 : ch2;
//if ch2 is out of boundary, ch1 is bigger, don't check rest, otherwise, see which one has bigger data

if (Heap[i].CompareTo(Heap[bigger]) < 0)
{
Swap(i, bigger);
Heapify(bigger);
}

}
}

class MinHeap<T> where T : IComparable<T>
{
private List<T> Heap;

public MinHeap()
{
Heap = new List<T>();
}

public T Min
{
get
{
if (Heap.Count == 0) throw new NullReferenceException();
else return Heap[0];
}
}

public bool IsEmpty()
{
return Heap == null || Heap.Count == 0;
}

public int Count
{
get
{
if (Heap == null) return 0;
else
{
return Heap.Count;
}
}
}

public void Insert(T data)
{

int ch = Heap.Count - 1; //ch for child
while (ch > 0)
{
int p = (ch - 1) / 2; //p for parent

if (Heap[ch].CompareTo(Heap[p]) < 0) //meaning child is smaller than parent -> Swap'm
{
Swap(p, ch);
ch = p;
}
else
break;
}
}
private void Swap(int p, int ch)
{
T temp = Heap[p];
Heap[p] = Heap[ch];
Heap[ch] = temp;
}

public T ExtractMin()
{
if (Heap == null || Heap.Count == 0) throw new NullReferenceException();
T ret = Heap[0];

Heap[0] = Heap[Heap.Count - 1];
Heap.RemoveAt(Heap.Count - 1);

Heapify(0);

return ret;
}
private void Heapify(int i) //i is parent
{
int ch1 = 2 * i + 1; //left child
int ch2 = 2 * i + 2; // right child

if (ch1 >= Heap.Count && ch2 >= Heap.Count) return;

int smaller = (ch2 >= Heap.Count) ? ch1 : (Heap[ch1].CompareTo(Heap[ch2]) < 0) ? ch1 : ch2;
//if ch2 is out of boundary, ch1 is smaller, don't check rest, otherwise, see which one has smaller data

if (Heap[i].CompareTo(Heap[smaller]) > 0)
{
Swap(i, smaller);
Heapify(smaller);
}
}
}

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.