...

/

Solution Review: Finding “K” Smallest Elements in the Array

Solution Review: Finding “K” Smallest Elements in the Array

Look over the solution review of the challenge given in the previous lesson.

Solution 1: removeMin() kk times

Press + to interact
main.cs
MinHeap.cs
using System;
using System.Collections.Generic;
namespace chapter_8
{
class excercise_2
{
static List<int> findKSmallest(int[] arr, int size, int k)
{
MinHeap<int> heap = new MinHeap<int>();
heap.buildHeap(arr, size);
List<int> output = new List<int>();
for (int i = 0; (i < k) && (i < size); i++)
{
output.Add(heap.getMin());
heap.removeMin();
}
return output;
}
static void Main(string[] args)
{
int size = 7;
int[] input = { 9, 4, 7, 1, -2, 6, 5 };
int [] output = findKSmallest(input, size, 3).ToArray();
for (int i = 0; i < output.Length; i++)
{
Console.Write(output[i] + " ");
}
return;
}
}
}

Here create a heap and then call the buildHeap (line 12) function to create a minimum heap from the given array. To find the k smallest elements in an array:

  • You get the minimum value from the heap.

  • Save the result to the vector output.

  • Remove the minimum value from the heap.

Repeat the same steps k times (provided k < size).

Time complexity

The time complexity of building a heap is ...