#algorithm discussion continued
Today we continue reading the flow networks. We were looking at maximum flows

Maximum flows can also be calculated using "push-relabel" method.

We reviewed relabel-to-front algorithm next. This algorithm improves the running time of the maximum flow problem by choosing the order of basic operations carefully and managing the network data structure efficiently.  We saw what admissible edges are. If a vertex u is overflowing and (u,v) is an admissible edge, the push (u,v) applies and while it does not create any new admissible edge, it may cause the edge u,v to become admissible. The admissible edges also applies to relabel operation
We also saw how the discharge operation takes place and how the relabel-to-front algorithm proceeds.
Since the relabel-to-front algorithm iterates on vertices other than the source or sink, this is best done in the form of topological sort of the vertices in the admissible network.

The Relabel to front algorithm computes maximum flow. It is in fact a push-relabel method. It uses discharge to do push and relabel only when they apply. The algorithm maintains the following invariant.
The vertex being discharged of its excess flow from the list of vertices has no vertex earlier in the list that has excess flow.
This means that the vertices are taken in topological sort order.

#preorder without recursion
void preorder(node root)
{
var current = root;
var stk = new Stack<node>();

while(current != null || stk.empty() == false)
{
if (current != null)
{
Console.Write(current.data);
stk.push(current);
current = current.left;
continue;
}
if (stk.empty() == false)
{
current = stk.pop();
current = current.right;
}
}
}

#postorder without recursion
void postorder(node root)
{
var current = root;
var stk = new Stack<node>();
Var last = null;
Var peek = null;
while(current != null || stk.empty() == false)
{
if (current != null)
{
stk.push(current);
current = current.left;
Continue;
}else
    Peek = stk.peek();

If(peek.right != null && peek.right!=last){
    Current = peek.right;
}
Else{
Console.Write(peek.data);
Last = stk.pop();

}
}
}
}

Given an array of n elements, where each element is at most k away from its target position, sort the array

Void sortK(ref List<int> A, int k)
{
Assert(A.count > k);
Var h = new Heap<int>();
For (int i =0: i < k && i < n; i++)
{
h.Add(A[i]);
}
Int i = k+1;
For(int j =0; j < n; j++)
{
   If (i < n){
       A[j] = h.replaceMin(A[i]);
       I ++;
}else{
      A[J]  = h.min()
}
}
}

The above also works for reverse order sorting except that we need to substitute min heap for max heap