Dark Mode

372 views

0 votes

> Use an array of size k as a min heap.

> With every element, compare it with min of heap, if found larger, insert in heap, else, ignore.

> Once the heap is full, if found larger than min of heap, delete the min and insert.

N = {8,4,2,6,1,5,6,9,10,3}, let k = 3 K = {}

N = {__8__,4,2,6,1,5,6,9,10,3} K ={8}

N = {8,__4__,2,6,1,5,6,9,10,3} K = {4,8}

N = {8,4,__2__,6,1,5,6,9,10,3} K = {2,4,8}

N = {8,4,2,__6__,1,5,6,9,10,3} K = {4,6,8}

N = {8,4,2,6,__1__,5,6,9,10,3} K = {4,6,8}

N = {8,4,2,6,1,__5__,6,9,10,3} K = {5,6,8}

N = {8,4,2,6,1,5,__6__,9,10,3} K = {5,6,8}

N = {8,4,2,6,1,5,6,__9__,10,3} K = {6,8,9}

N = {8,4,2,6,1,5,6,9,__10__,3} K = {8,9,10}

N = {8,4,2,6,1,5,6,9,10,__3__} K = {8,9,10}

2

3 votes

**Answer will be max heap of size n.**

We can access first max element from max heap in O(1).

After that just delete k max element from heap and after every delete heapify the tree make sure it is max heap, which will take O(logn).

So for K element time complexity will be O(klogn). And K is constant so O(logn).

1