Minimize Cash Flow

// C# program to Minimize Cash Flow among a given set
// of friends who have borrowed money from each other.
using System;
using System.Collections.Generic;

class GfG {

    // Function to minimize cash flow
    static int[][] minCashFlow(int[][] transaction) {
        int n = transaction.Length;

        PriorityQueue<int[]> debtors = 
        new PriorityQueue<int[]>(new Comparer());
        PriorityQueue<int[]> creditors = 
        new PriorityQueue<int[]>(new Comparer());
        
        // Calculate net amount for each person
        for (int personId = 0; personId < n; personId++) {
            int netAmount = 0;
            
            // Add all incoming money
            for (int fromPerson = 0; fromPerson < n; fromPerson++)
                netAmount += transaction[fromPerson][personId];
            
            // Subtract all outgoing money
            for (int toPerson = 0; toPerson < n; toPerson++)
                netAmount -= transaction[personId][toPerson];
            
            // If net amount is negative, person needs to give money
            if (netAmount < 0)
                debtors.Enqueue(new int[] { Math.Abs(netAmount), personId });
            
            // If net amount is positive, person needs to receive money
            else if (netAmount > 0)
                creditors.Enqueue(new int[] { netAmount, personId });
        }

        // Initialize result matrix with zeros
        int[][] result = new int[n][];
        for (int i = 0; i < n; i++)
            result[i] = new int[n];

        // Process all transactions until no more debtors left
        while (debtors.Count > 0) {
            int[] debtor = debtors.Dequeue();
            int[] creditor = creditors.Dequeue();
            int debtAmount = debtor[0];
            int creditAmount = creditor[0];
            int debtorId = debtor[1];
            int creditorId = creditor[1];

            // Find minimum of debt and credit amounts
            int transferAmount = Math.Min(debtAmount, creditAmount);

            // Record the transaction in result matrix
            result[debtorId][creditorId] = transferAmount;

            // Update remaining amounts
            debtAmount -= transferAmount;
            creditAmount -= transferAmount;

            // If debtor still has debt remaining, put back in queue
            if (debtAmount > 0)
                debtors.Enqueue(new int[] { debtAmount, debtorId });

            // If creditor still needs to receive more, put back in queue
            else if (creditAmount > 0)
                creditors.Enqueue(new int[] { creditAmount, creditorId });
        }

        return result;
    }

    static void Main() {
        int n = 3;
        int[][] transaction = new int[][] {
            new int[] {0, 1000, 2000},
            new int[] {0, 0, 5000},
            new int[] {0, 0, 0}
        };

        int[][] result = minCashFlow(transaction);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                Console.Write(result[i][j] + " ");
            }
            Console.WriteLine();
        }
    }
}

// Custom comparator class for max heap
class Comparer : IComparer<int[]> {
    public int Compare(int[] a, int[] b) {
        return b[0].CompareTo(a[0]);
    }
}

// Custom Priority queue 
class PriorityQueue<T> {
    private List<T> heap;
    private IComparer<T> comparer;

    public PriorityQueue(IComparer<T> comparer = null) {
        this.heap = new List<T>();
        this.comparer = comparer ?? Comparer<T>.Default;
    }

    public int Count => heap.Count;

    // Enqueue operation
    public void Enqueue(T item) {
        heap.Add(item);
        int i = heap.Count - 1;
        while (i > 0) {
            int parent = (i - 1) / 2;
            if (comparer.Compare(heap[parent], heap[i]) <= 0)
                break;
            Swap(parent, i);
            i = parent;
        }
    }

    // Dequeue operation
    public T Dequeue() {
        if (heap.Count == 0)
            throw new InvalidOperationException("Priority queue is empty.");
        T result = heap[0];
        int last = heap.Count - 1;
        heap[0] = heap[last];
        heap.RemoveAt(last);
        last--;
        int i = 0;
        while (true) {
            int left = 2 * i + 1;
            if (left > last)
                break;
            int right = left + 1;
            int minChild = left;
            if (right <= last && comparer.Compare(heap[right], heap[left]) < 0)
                minChild = right;
            if (comparer.Compare(heap[i], heap[minChild]) <= 0)
                break;
            Swap(i, minChild);
            i = minChild;
        }
        return result;
    }

    // Swap two elements in the heap
    private void Swap(int i, int j) {
        T temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }
}