# beat 100% c# submission with correct heap implementation.

• in another post, I submit a solution which use BinarySearch to implement PQ. however, it doesn't necessary to maintain a sorted list. so the performance is a little slow.
I check previous fastest submission, but find their implementation of heap was wrong.
I decide to rewrite the solution with correct heap implementation. It beat 100% c# submission now.
below is the solution.

``````public class Solution {
public int[,] directions = new int[,] { {1,0 }, {-1,0 }, {0,1 }, {0,-1 } };
public int TrapRainWater(int[,] heightMap)
{
var total = 0;
var m = heightMap.GetLength(0);
var n = heightMap.GetLength(1);
var visitied = new bool[m, n];
var q = new PriorityQueue<int[]>(16, Comparer<int[]>.Create((a, b) => a[2] - b[2]));
for (var i = 0; i < m; ++i)
{
q.Push(new int[] { i, 0, heightMap[i, 0] });
q.Push(new int[] { i, n-1, heightMap[i, n-1] });
visitied[i, 0] = visitied[i, n - 1] = true;// don't forget to set visited when init the queue
}

for(var i=0;i< n; ++i)
{
q.Push(new int[] { 0, i, heightMap[0, i] });
q.Push(new int[] { m-1, i, heightMap[m-1, i] });
visitied[0, i] = visitied[m - 1, i] = true;
}

while (q.Count > 0)
{
var cell = q.Pop();
for(var i = 0; i < 4; ++i)
{
var x = cell[0] + directions[i, 0];
var y = cell[1] + directions[i, 1];
if (x < 0 || x == m || y < 0 || y == n || visitied[x, y]) continue;
total += Math.Max(0, cell[2] - heightMap[x, y]);
q.Push(new int[] { x, y, Math.Max(cell[2], heightMap[x,y]) });
visitied[x, y] = true;
}
}

}

/// <summary>
/// Mini Heap as default comparasion direction (a,b)=>a-b;
/// Max Heap when reverse default direction (a,b)=> b-a;
/// </summary>
/// <typeparam name="T"></typeparam>
public class PriorityQueue<T>
{
internal IComparer<T> comparer;

internal T[] heap;
public int Count { get; private set; }

public PriorityQueue(int capacity = 16, IComparer<T> comparer = null)
{
this.comparer = comparer ?? Comparer<T>.Default;
this.heap = new T[capacity];
}

/// <summary>
/// To add an element to a heap we must perform an up-heap operation (also known as bubble-up, percolate-up, sift-up, trickle-up, heapify-up, or cascade-up), by following this algorithm:
//  1.Add the element to the bottom level of the heap.
/// 2.Compare the added element with its parent; if they are in the correct order, stop.
/// 3.If not, swap the element with its parent and return to the previous step.
/// be careful:
/// The downward-moving node is swapped with the larger of its children in a max-heap (in a min-heap it would be swapped with its smaller child), until it satisfies the heap property in its new position. This functionality is achieved by the Max-Heapify function as defined below in pseudocode for an array-backed heap A of length heap_length[A]. Note that "A" is indexed starting at 1.
/// </summary>
/// <param name="v"></param>
public void Push(T v)
{
if (Count >= heap.Length)
{
Array.Resize(ref heap, Count * 2);
}

heap[Count] = v;
Count++;
SiftUp();
}

/// <summary>
/// The procedure for deleting the root from the heap (effectively extracting the maximum element in a max-heap or the minimum element in a min-heap) and restoring the properties is called down-heap (also known as bubble-down, percolate-down, sift-down, trickle down, heapify-down, cascade-down, and extract-min/max).
/// 1. Replace the root of the heap with the last element on the last level.
/// 2. Compare the new root with its children; if they are in the correct order, stop.
/// 3. If not, swap the element with one of its children and return to the previous step. (Swap with its smaller child in a min-heap and its larger child in a max-heap.)
/// </summary>
/// <returns></returns>
public T Pop()
{
var v = Top();
heap[0] = heap[--Count];
if (Count > 1)
{
SiftDown();
}

return v;
}

public T Top()
{
if (Count > 0)
{
return heap[0];
}

throw new InvalidOperationException("");
}

void SiftUp()
{
var n = Count - 1;
var v = heap[n];

while (n > 0)
{
var parent = (n - 1) / 2;
// for min heap
if (comparer.Compare(v, heap[parent]) < 0)
{
heap[n] = heap[parent];
n = parent;
}
else
{
break;
}
}

heap[n] = v;
}

void SiftDown()
{
var n = 0;
var v = heap[n];

while (n < Count)
{
var left = n * 2 + 1;
var right = n * 2 + 2;
var smallest = n;
if(left<Count&& comparer.Compare(v, heap[left]) > 0)
{
smallest = left;
}

if(right<Count&&comparer.Compare(v, heap[right]) > 0&& ((left<Count && comparer.Compare(heap[left], heap[right]) > 0) || (left>=Count)))
{
smallest = right;
}

if (smallest == n)
{
break;//cannot find child smaller than heap[n]; stop siftdown
}

heap[n] = heap[smallest]; //otherwise let heap[parent] = heap[smallest], and move parent index to smallest
n = smallest;
}

heap[n] = v;
}
}
}
``````

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