...
/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.
We'll cover the following...
Solution 1: removeMin()
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 ...