https://leetcode.com/problems/sliding-window-median/

Please check for performance. and coding style, no need to check maximum and minimum heaps.

median is the mean of the two mean values.

Examples: (2,3,4), the median is 3

(2,3), the median is (2 + 3) / 2 = 2.5

Given a set of numbers, there is a sliding window of size k that is

moving from the left of the matrix to the right. You can only

See the k numbers in the window. Every time the sliding window is moved

right in one position. Your job is to generate the median matrix for each

window in the original matrix.

For example, given nums = (1,3, -1, -3,5,3,6,7) and k = 3.

So return the median sliding window as (1, -1, -1,3,5,6).

Note: You can assume that k is always valid, that is: k is always smaller than

size of the input array for the non-empty array. Answers within 10 ^ -5 of

The actual value will be accepted as correct.

**TESTS**

```
///
/// https://leetcode.com/problems/sliding-window-median/
///
(TestClass)
public class SlidingWindowMedianTest
{
(TestMethod)
public void ExampleTest()
{
int() nums = { 1, 3, -1, -3, 5, 3, 6, 7 };
int k = 3;
double() expected = { 1, -1, -1, 3, 5, 6 };
SlidingWindowMedianWith2Heaps heaps = new SlidingWindowMedianWith2Heaps();
var res = heaps.MedianSlidingWindow(nums, k);
CollectionAssert.AreEqual(expected, res);
}
(TestMethod)
public void ExampleTestFailed()
{
int() nums = { 1, 4, 2, 3 };
int k = 4;
double() expected = { 2.5 };
SlidingWindowMedianWith2Heaps heaps = new SlidingWindowMedianWith2Heaps();
var res = heaps.MedianSlidingWindow(nums, k);
CollectionAssert.AreEqual(expected, res);
}
(TestMethod)
public void ExampleTestOverFlow()
{
int() nums = { 2147483647, 2147483647 };
int k = 2;
double() expected = { 2147483647.0 };
SlidingWindowMedianWith2Heaps heaps = new SlidingWindowMedianWith2Heaps();
var res = heaps.MedianSlidingWindow(nums, k);
CollectionAssert.AreEqual(expected, res);
}
(TestMethod)
public void ExampleFailed2()
{
int() nums = { 5, 2, 2, 7, 3, 7, 9, 0, 2, 3 };
int k = 9;
double() expected = { 3.0, 3.0 };
SlidingWindowMedianWith2Heaps heaps = new SlidingWindowMedianWith2Heaps();
var res = heaps.MedianSlidingWindow(nums, k);
CollectionAssert.AreEqual(expected, res);
}
}
```

**CODE Answering the question**

```
public class SlidingWindowMedianWith2Heaps
{
public BinaryMaxHeap MaxHeap;
public BinaryMinHeap MinHeap;
public double() MedianSlidingWindow(int() nums, int k)
{
MaxHeap = new BinaryMaxHeap(k);
MinHeap = new BinaryMinHeap(k);
int n = nums.Length - k + 1;
if (n <= 0)
{
return new double(n);
}
var result = new double(n);
for (int i = 0; i <= nums.Length; i++)
{
if (i >= k)
{
result(i - k) = GetMedian();
Remove(nums(i - k));
}
if (i < nums.Length)
{
Add(nums(i));
}
}
return result;
}
private void Add(int num)
{
if (num < GetMedian())
{
MaxHeap.InsertKey(num);
}
else
{
MinHeap.InsertKey(num);
}
if (MaxHeap.Count > MinHeap.Count)
{
MinHeap.InsertKey(MaxHeap.ExtractMax());
}
if (MinHeap.Count - MaxHeap.Count > 1)
{
MaxHeap.InsertKey(MinHeap.ExtractMin());
}
}
private void Remove(int num)
{
if (num < GetMedian())
{
MaxHeap.DeleteKey(num);
}
else
{
MinHeap.DeleteKey(num);
}
if (MaxHeap._heapSize > MinHeap._heapSize)
{
MinHeap.InsertKey(MaxHeap.ExtractMax());
}
if (MaxHeap._heapSize - MinHeap._heapSize > 1)
{
MaxHeap.InsertKey(MinHeap.ExtractMin());
}
}
private double GetMedian()
{
if (MaxHeap.Count == 0 && MinHeap.Count == 0)
{
return 0;
}
if (MaxHeap.Count == MinHeap.Count)
{
return (MaxHeap.GetMax() + (double) MinHeap.GetMin()) / 2.0;
}
else
{
return MinHeap.GetMin();
}
}
}
```

**MaxHeap**

```
public class BinaryMaxHeap
{
private readonly int() _heapArr;
private readonly int _capacity;
public uint _heapSize; //current size of heap
public BinaryMaxHeap(int capacity)
{
_capacity = capacity;
_heapSize = 0;
_heapArr = new int(capacity);
}
public void InsertKey(int key)
{
if (_heapSize == _capacity)
{
throw new StackOverflowException("overflow can't insert key");
}
//insert the new key at the end
_heapSize++;
uint i = _heapSize - 1;
_heapArr(i) = key;
// fix the heap as max heap
// Fix the max heap property if it is violated
while (i != 0 && _heapArr(Parent(i)) < _heapArr(i)) //bubble is generic specific
{
Swap(i, Parent(i));
i = Parent(i);
}
}
public int ExtractMax()
{
if (_heapSize <= 0)
{
return 0;
}
if (_heapSize == 1)
{
_heapSize--;
return _heapArr(0);
}
// Store the minimum value, and remove it from heap
int root = _heapArr(0);
_heapArr(0) = _heapArr(_heapSize - 1);
_heapSize--;
Heapify(0);
return root;
}
private void Heapify(uint i)
{
uint l = Left(i);
uint r = Right(i);
uint largest = i;
if (l < _heapSize && _heapArr(i) < _heapArr(l))
{
largest = l;
}
if (r < _heapSize && _heapArr(largest) < _heapArr(r))
{
largest = r;
}
if (largest != i)
{
Swap(i, largest);
Heapify(largest);
}
}
private void Swap(uint key1, uint key2)
{
int temp = _heapArr(key2);
_heapArr(key2) = _heapArr(key1);
_heapArr(key1) = temp;
}
private uint Parent(uint i)
{
return (i - 1) / 2;
}
private uint Right(uint i)
{
return 2 * i + 2;
}
private uint Left(uint i)
{
return 2 * i + 1;
}
public int GetMax()
{
return _heapArr(0);
}
public uint Count
{
get { return _heapSize; }
}
public void DeleteKey(int key)
{
uint index = 0;
for (uint i = 0; i < _heapSize; i++)
{
if (_heapArr(i) == key)
{
index = i;
break;
}
}
DeleteKeyAtIndex(index);
}
///
/// This function deletes key at index index. It first increases value to plus
/// infinite, then calls extractMax()
///
private void DeleteKeyAtIndex(uint index)
{
IncreaseKey(index, int.MaxValue);
ExtractMax();
}
private void IncreaseKey(uint i, int newValue)
{
_heapArr(i) = newValue;
while (i != 0 && _heapArr(Parent(i)) < _heapArr(i)) //bubble is generic specific
{
Swap(i, Parent(i));
i = Parent(i);
}
}
}
```

**MinHeap**

```
public class BinaryMinHeap
{
private readonly int() _heapArr;// pointer to array of elements in heap
private readonly int _capacity; // maximum possible size of min heap
public uint _heapSize; // Current number of elements in min heap
public BinaryMinHeap(int capacity)
{
_capacity = capacity;
_heapSize = 0;
_heapArr = new int(capacity);
}
public void InsertKey(int key)
{
if (_heapSize == _capacity)
{
throw new StackOverflowException("overflow can't insert key");
}
//insert the new key at the end
_heapSize++;
uint i = _heapSize - 1;
_heapArr(i) = key;
//fix the heap as min heap
// Fix the min heap property if it is violated
while (i != 0 && _heapArr(Parent(i)) > _heapArr(i)) //bubble is generic specific
{
Swap(i, Parent(i));
i = Parent(i);
}
}
public void DeleteKey(int key)
{
uint index = 0;
for (uint i = 0; i < _heapSize; i++)
{
if (_heapArr(i) == key)
{
index = i;
break;
}
}
DeleteKeyAtIndex(index);
}
///
/// This function deletes key at index index. It first reduced value to minus
/// infinite, then calls extractMin()
///
public void DeleteKeyAtIndex(uint index)
{
DecreaseKey(index, int.MinValue);
ExtractMin();
}
public void DecreaseKey(uint i, int newValue)
{
_heapArr(i) = newValue;
while (i != 0 && _heapArr(Parent(i)) > _heapArr(i)) //bubble is generic specific
{
Swap(i, Parent(i));
i = Parent(i);
}
}
///
/// you switch the root with the last index in the array, the end of the heap
/// and you heapify the root node.
///
///
public int ExtractMin()
{
if (_heapSize <= 0)
{
return int.MaxValue;
}
if (_heapSize == 1)
{
_heapSize--;
return _heapArr(0);
}
// Store the minimum value, and remove it from heap
int root = _heapArr(0);
_heapArr(0) = _heapArr(_heapSize - 1);
_heapSize--;
Heapify(0);
return root;
}
///
/// the first call is done with index 0,
/// since this is recursive function you compare to right subtree and left subtree
/// you choose the lower node and swap the root with it, than you call
/// the same function from the last index you swapped with
///
///
private void Heapify(uint i)
{
uint l = Left(i);
uint r = Right(i);
uint smallest = i;
if (l < _heapSize && _heapArr(l) < _heapArr(i))
{
smallest = l;
}
if (r < _heapSize && _heapArr(r) < _heapArr(smallest))
{
smallest = r;
}
if (smallest != i)
{
Swap(i, smallest);
Heapify(smallest);
}
}
private uint Right(uint i)
{
return 2 * i + 2;
}
private uint Left(uint i)
{
return 2 * i + 1;
}
private uint Parent(uint i)
{
return (i - 1) / 2;
}
private void Swap(uint key1, uint key2)
{
int temp = _heapArr(key2);
_heapArr(key2) = _heapArr(key1);
_heapArr(key1) = temp;
}
public int GetMin()
{
return _heapArr(0);
}
public uint Count
{
get { return _heapSize; }
}
}
```