Find K biggest numbers in the array

Question

I was trying to implement method number 2, from this article.

Method 2 (Use temporary array) K largest elements from arr[0..n-1]

1. Store the first k elements in a temporary array temp[0..k-1].
2. Find the smallest element in temp[], let the smallest element be min.
3. For each element x in arr[k] to arr[n-1] If x is greater than the min then remove min from temp[] and insert x.
4. Print final k elements of temp[]

Time Complexity: O((n-k)*k). If we want the output sorted then O((n-k)*k + klogk)

Please comment on the complexity and runtime speed. Can I improve my implementation in that sense? I was trying to get O((n-k)*k).

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

namespace JobInterviewTests
{

    //Design an algorithm to find K biggest numbers in the array.
    [TestClass]
    public class KBiggestNumbers
    {
        [TestMethod]
        public void FindKBiggestNumbersTest()
        {
            int[] testArray = new[] { 7, 2, 4, 4, 3, 6, 1, 8, 9, 10, 11 };
            int k = 5;
            int[] result = FindKBiggestNumbers(testArray, k);
            int[] expectedResult = new[] { 7,8,9,10,11 };
            CollectionAssert.AreEqual(expectedResult, result);
        }

        private int[] FindKBiggestNumbers(int[] testArray, int k)
        {
            int[] result = new int[k];
            for (int i = 0; i < testArray.Length; i++)
            {
                //if bigger than the smallest node
                if (testArray[i] <= result[0])
                {
                    continue;
                }
                else
                {
                    //if bigger than all?
                    if (testArray[i] > result[k - 1])
                    {
                        for (int l = 0; l < k - 1; l++)
                        {
                            result[l] = result[l + 1];
                        }
                        result[k - 1] = testArray[i];
                    }
                    else
                    {

                        //Naive way
                        //for (int j = 0; j < k-1; j++)
                        //{
                        //    if (testArray[i] > result[j] && testArray[i] <= result[j + 1])
                        //    {
                        //        for (int l = 0; l < j; l++)
                        //        {
                        //            result[l] = result[l + 1];
                        //        }
                        //        result[j] = testArray[i];
                        //        break;
                        //    }
                        //}

                        //binary search
                        int indexLeft = 0;
                        int indexRight = k-1;

                        int currIndex = 0;
                        //10 20 30 40 50 - > place 33 
                        while (indexRight- indexLeft >1)
                        {
                            currIndex = (indexRight + indexLeft)/2;
                            if (testArray[i] >= result[currIndex])
                            {
                                indexLeft = currIndex;
                            }
                            else
                            {
                                indexRight = currIndex;
                            }

                        }

                        for (int l = 0; l < currIndex; l++)
                        {
                            result[l] = result[l + 1];
                        }
                        result[currIndex] = testArray[i];
                    }
                }
            }
            return result;
        }
    }
}

Answer 1

Store the first k elements in a temporary array temp[0..k-1]

You are not doing that

Find the smallest element in temp[], let the smallest element be min

You are not doing that

For each element x in arr[k] to arr[n-1]...

You are starting on 0 because you skipped step 1

Nothing in there about a binary search
Not less operations the with the shifts

This

if (testArray[i] <= result[0])
{
    continue;
}
else
{

Can be

if (testArray[i] > result[0])
{

Other than that looks good

Just following what I think are the instructions
It is \$\mathcal{O}(n \times k)\$ as the first k elements are not free

private int[] FindKBiggestNumbersM(int[] testArray, int k)
{
    int[] result = new int[k];
    int indexMin = 0;
    result[indexMin] = testArray[0];
    int min = result[indexMin];

    for (int i = 1; i < testArray.Length; i++)
    {
        if(i < k)
        {
            result[i] = testArray[i];
            if (result[i] < min)
            {
                min = result[i];
                indexMin = i;
            }
        }
        else if (testArray[i] > min)
        {
            min = testArray[i];
            result[indexMin] = min;
            for (int r = 0; r < k; r++)
            {
                if (result[r] < min)
                {
                    min = result[r];
                    indexMin = r;
                }
            }
        }
    }
    return result;
}

Answer 2

A bug

On the array of 10 elements

19 8 5 9 15 10 8 2 6 1

when computing 8 largest numbers, your version returns

2 5 8 8 9 10 15 19
^ 
wrong, should be 6

when the correct answer is

5 6 8 8 9 10 15 19.

Performance

My idea was to build a maximum heap of the entire input array (which runs, according to Introduction to Algorithms, in \$\Theta(n)\$), after which to peak \$k\$ maximum elments; this algorithm runs in \$\Theta(n + k \log n)\$. That is how:

using System;
using System.Linq;

namespace CRKBiggestNums
{
    public class KBiggestNumbers
    {
        public static int[] FindKBiggestNumbers(int[] testArray, int k)
        {
            int[] result = new int[k];
            for (int i = 0; i < testArray.Length; i++)
            {
                //if bigger than the smallest node
                if (testArray[i] <= result[0])
                {
                    continue;
                }
                else
                {
                    //if bigger than all?
                    if (testArray[i] > result[k - 1])
                    {
                        for (int l = 0; l < k - 1; l++)
                        {
                            result[l] = result[l + 1];
                        }
                        result[k - 1] = testArray[i];
                    }
                    else
                    {
                        //binary search
                        int indexLeft = 0;
                        int indexRight = k - 1;

                        int currIndex = 0;
                        //10 20 30 40 50 - > place 33 
                        while (indexRight - indexLeft > 1)
                        {
                            currIndex = (indexRight + indexLeft) / 2;
                            if (testArray[i] >= result[currIndex])
                            {
                                indexLeft = currIndex;
                            }
                            else
                            {
                                indexRight = currIndex;
                            }

                        }

                        for (int l = 0; l < currIndex; l++)
                        {
                            result[l] = result[l + 1];
                        }
                        result[currIndex] = testArray[i];
                    }
                }
            }

            return result;
        }

        public static int[] FindKBiggestNumbers2(int[] array, int k)
        {
            BuildMaxHeap(array);
            int[] result = new int[k];
            int heapSize = array.Length;

            for (int i = 0; i < k - 1; ++i)
            {
                result[i] = array[0];
                array[0] = array[--heapSize];
                MaxHeapify(array, 0, heapSize);
            }

            result[result.Length - 1] = array[0];
            return result;
        }

        private static void BuildMaxHeap(int[] array)
        {
            for (int i = array.Length / 2; i >= 0; --i)
            {
                MaxHeapify(array, i, array.Length);
            }
        }

        private static void MaxHeapify(int[] array, int index, int heapSize)
        {
            int leftChildIndex = GetLeftIndex(index);
            int rightChildIndex = leftChildIndex + 1;
            int maxChildIndex = index;
            int target = array[index];

            while (true)
            {
                if (leftChildIndex < heapSize)
                {
                    if (array[leftChildIndex] > target)
                    {
                        maxChildIndex = leftChildIndex;
                    }
                }

                if (maxChildIndex == index)
                {
                    if (rightChildIndex < heapSize)
                    {
                        if (array[rightChildIndex] > target)
                        {
                            maxChildIndex = rightChildIndex;
                        }
                    }
                }
                else
                {
                    if (rightChildIndex < heapSize)
                    {
                        if (array[rightChildIndex] > array[maxChildIndex])
                        {
                            maxChildIndex = rightChildIndex;
                        }
                    }
                }

                if (maxChildIndex == index)
                {
                    array[maxChildIndex] = target;
                    return;
                }

                array[index] = array[maxChildIndex];
                index = maxChildIndex;
                leftChildIndex = GetLeftIndex(index);
                rightChildIndex = leftChildIndex + 1;
            }
        }

        private static int GetLeftIndex(int index)
        {
            return (index << 1) + 1;
        }

        private static long GetMilliseconds()
        {
            return DateTime.Now.Ticks / TimeSpan.TicksPerMillisecond;
        }

        public static void Main(string[] args)
        {
            Random random = new Random();
            int[] array1 = new int[1000 * 1000];
            int[] array2 = new int[array1.Length];

            for (int i = 0; i != array1.Length; ++i)
            {
                int element = random.Next(20);
                array1[i] = element;
                array2[i] = element;
            }

            int k = 10 * 1000;
            var start = GetMilliseconds();
            int[] result1 = FindKBiggestNumbers(array1, k);
            var end = GetMilliseconds();

            Console.WriteLine("OP method in {0} milliseconds.", end - start);

            start = GetMilliseconds();
            int[] result2 = FindKBiggestNumbers2(array2, k);
            end = GetMilliseconds();

            Console.WriteLine("coderodde method in {0} milliseconds.", end - start);

            Array.Sort(result1);
            Array.Sort(result2);

            Console.WriteLine("The algorithms agree: {0}.", result1.SequenceEqual(result2));
        }
    }
}

Finally, the performance figures for \$n = 1000000, k = 10000\$ speak for themselves:

OP method in 1692 milliseconds.
coderodde method in 69 milliseconds.

Hope that helps.

Answer 3

There is a bug in the above code because of which FindKBiggestNumbers and FindKBiggestNumbers2 give different results. Actually bug is there in FindKBiggestNumbers function. Here is the modified code for FindKBiggestNumbers

public static int[] FindKBiggestNumbers(int[] testArray, int k)
{
    int[] result = new int[k];
    for (int i = 0; i < testArray.Length; i++)
    {
        //if bigger than the smallest node
        if (testArray[i] <= result[0])
        {
            continue;
        }
        else
        {
            //if bigger than all?
            if (testArray[i] > result[k - 1])
            {
                for (int l = 0; l < k - 1; l++)
                {
                    result[l] = result[l + 1];
                }
                result[k - 1] = testArray[i];
            }
            else
            {
                //binary search
                int indexLeft = 0;
                int indexRight = k - 1;

                int currIndex = (indexRight + indexLeft) / 2; ;
                //10 20 30 40 50 - > place 33 
                while (indexRight - indexLeft > 1)
                {

                    if (testArray[i] >= result[currIndex])
                    {
                        indexLeft = currIndex;
                    }
                    else
                    {
                        indexRight = currIndex;
                    }
                currIndex = (indexRight + indexLeft) / 2;
            }

                for (int l = 0; l < currIndex; l++)
                {
                    result[l] = result[l + 1];
                }
                result[currIndex] = testArray[i];
            }
        }
    }

    return result;
}