LeetCode: Minimum cost to hire k workers

https://leetcode.com/problems/minimum-cost-to-hire-k-workers/

There are N workers. The i-th worker has a quality[i] and a minimum wage expectation wage[i].

Now we want to hire exactly K workers to form a paid group. When hiring a group of K workers, we must pay them according to the following rules:

1. Every worker in the paid group should be paid in the ratio of their quality compared to other workers in the paid group.
2. Every worker in the paid group must be paid at least their minimum wage expectation.

Return the least amount of money needed to form a paid group satisfying the above conditions.

Example 1:

Input: quality = [10,20,5], wage = [70,50,30], K = 2
Output: 105.00000
Explanation: We pay 70 to 0-th worker and 35 to 2-th worker.

Example 2:

Input: quality = [3,1,10,10,1], wage = [4,8,2,2,7], K = 3
Output: 30.66667
Explanation: We pay 4 to 0-th worker, 13.33333 to 2-th and 3-th workers seperately. 

Note:

1. 1 <= K <= N <= 10000, where N = quality.length = wage.length
2. 1 <= quality[i] <= 10000
3. 1 <= wage[i] <= 10000
4. Answers within \$10^{-5}\$ of the correct answer will be considered correct.

This is one of the hardest problems I met on leetcode

Please review the code as if this was 45 minute interview. Performance is the main issue here. this solution is same as the leetcode solution, I have one question also is why not use use maxHeap and do the "trick" of multiplying the quality with -1, before pushing into the heap?

using System;
using Heap;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace ArrayQuestions
{
    /// <summary>
    /// https://leetcode.com/problems/minimum-cost-to-hire-k-workers/
    /// </summary>
    [TestClass]
    public class MinimumCostToHirekWorkers
    {
        [TestMethod]
        public void MinCost2()
        {
            int[] quality = { 10, 20, 5 };
            int[] wage = { 70, 50, 30 };
            int k = 2;
           
            Assert.AreEqual(105.0, MincostToHireWorkersHeap(quality, wage, k));

        }

        [TestMethod]
        public void MinCost3()
        {
            int[] quality = { 3, 1, 10, 10, 1 };
            int[] wage = { 4, 8, 2, 2, 7 };
            int k = 3;
           
            Assert.AreEqual(30.66667, MincostToHireWorkersHeap(quality, wage, k), 0.001);

        }

   

        public double MincostToHireWorkersHeap(int[] quality, int[] wage, int K)
        {
            Worker[] workers = new Worker[quality.Length];
            for (int i = 0; i < quality.Length; i++)
            {
                workers[i] = new Worker(quality[i], wage[i]);
            }
            //we sort the workers by their ratio, low ratio X low quality == low cost
            Array.Sort(workers);
            double ans = double.MaxValue;

            int sumq = 0;
            BinaryHeap heap = new BinaryHeap((uint)quality.Length);
            foreach (var worker in workers)
            {
                //we push into the min heap the negative value of quality
                // this is a max heap after that
                heap.InsertKey(-1 * worker.Quality);
                sumq += worker.Quality;
                //if we have more than k we will remove the biggest negative value
                // which is the height quality
                if (heap.Count > K)
                {
                    sumq += heap.ExtractMin();
                }

                // we compute the sum with this worker ratio
                if (heap.Count == K)
                {
                    ans = Math.Min(ans, sumq * worker.Ratio);
                }
            }

            return ans;
        }
    }

    public class Worker : IComparable<Worker>
    {
        public int Quality;
        public int Wage;

        public Worker(int q, int w)
        {
            Quality = q;
            Wage = w;
        }
        public double Ratio
        {
            get { return (double)Wage / Quality; }
        }

        public int CompareTo(Worker other)
        {
            if (Ratio > other.Ratio)
            {
                return 1;
            }
            if (Ratio < other.Ratio)
            {
                return -1;
            }
            return 0;
        }
    }
}

This is the code for the MinHeap no need to review it, I assume that you don't need to implement this is a 45 minutes interview

 public class BinaryHeap
    {
        private readonly int[] _harr;// pointer to array of elements in heap
        private readonly uint _capacity; // maximum possible size of min heap
        public uint _heapSize; // Current number of elements in min heap

        public BinaryHeap(uint capacity)
        {
            _capacity = capacity;
            _heapSize = 0;
            _harr = 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;
            _harr[i] = key;

            //fix the heap  as min heap
            // Fix the min heap property if it is violated
            while (i != 0 && _harr[Parent(i)] > _harr[i]) //bubble is generic specific
            {
                Swap(i, Parent(i));
                i = Parent(i);
            }
        }

        /// <summary>
        /// This function deletes key at index i. It first reduced value to minus
        /// infinite, then calls extractMin()
        /// </summary>
        public void DeleteKey(uint i)
        {
            DecreaseKey(i, Int32.MinValue);
            ExtractMin();
        }

        public void DecreaseKey(uint i, int newValue)
        {
            _harr[i] = newValue;
            while (i != 0 && _harr[Parent(i)] > _harr[i]) //bubble is generic specific
            {
                Swap(i, Parent(i));
                i = Parent(i);
            }
        }
        /// <summary>
        /// you switch the root with the last index in the array, the end of the heap
        /// and you heapify the root node.
        /// </summary>
        /// <returns></returns>
        public int ExtractMin()
        {
            if (_heapSize <= 0)
            {
                return Int32.MaxValue;
            }
            if (_heapSize == 1)
            {
                _heapSize--;
                return _harr[0];
            }

            // Store the minimum value, and remove it from heap
            int root = _harr[0];
            _harr[0] = _harr[_heapSize - 1];
            _heapSize--;
            Heapify(0);
            return root;
        }
        /// <summary>
        /// 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
        /// </summary>
        /// <param name="i"></param>
        private void Heapify(uint i)
        {
            uint l = Left(i);
            uint r = Right(i);
            uint smallest = i;
            if (l < _heapSize && _harr[l] < _harr[i])
            {
                smallest = l;
            }
            if (r < _heapSize && _harr[r] < _harr[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 = _harr[key2];
            _harr[key2] = _harr[key1];
            _harr[key1] = temp;
        }

        public int GetMin()
        {
            return _harr[0];
        }
        public uint Count
        {
            get { return _heapSize; }
        }
    }