CJCoding With Joseph
15free / daySign inCreate account

Keep Only the k Largest Values Seen So Far

Write keep_largest. It is called once for every number in a long stream. The heap it is given has room for exactly k values, and after every call it must hold the k LARGEST numbers seen so far (or all of them, when fewer than k have arrived).

Reminder: how this min heap is stored. A min_heap is a struct with three fields: capacity (the most values it can hold), count (how many it holds now) and values (a pointer to an array made with malloc). The heap is a complete binary tree kept in that array, filled row by row with no gaps, so only slots 0 to count - 1 are in use. Every parent is smaller than or equal to its children, so the smallest value is always at index 0. For the value at index i, the parent is at (i - 1) / 2 and the children are at 2 * i + 1 and 2 * i + 2.

It sounds backwards to use a MIN heap to keep the LARGEST values, but it is exactly right. The root of the heap is the smallest of the values being kept, which makes it the one to beat. A new number that is not bigger than the root cannot be one of the k largest and is ignored. A number that is bigger pushes the root out and takes a place in the heap.

k = 3, the stream so far: 5 1 9         the heap keeps 1 5 9 (root 1)

  next number 3:  3 > 1, so 1 is pushed out      keeps 3 5 9 (root 3)
  next number 2:  2 is not bigger than 3         ignored
  next number 7:  7 > 3, so 3 is pushed out      keeps 5 7 9 (root 5)

        5
       / \           the root is always the smallest value that is still kept:
      7   9          the k-th largest number seen so far

min_heap_insert and min_heap_replace are already written. Replace does the "push the root out and put this in" step in one call.

Requirements: 1. While the heap is not full, insert the value. 2. When the heap is full and the value is bigger than the root, replace the root with it. 3. Otherwise do nothing. A value equal to the root is not kept. 4. A heap with a capacity of 0 keeps nothing.

Do NOT write a main function.

Expected Output:

after 5: holding 1, smallest kept 5
after 1: holding 2, smallest kept 1
after 9: holding 3, smallest kept 1
after 3: holding 3, smallest kept 3
after 2: holding 3, smallest kept 3
after 7: holding 3, smallest kept 5
after 8: holding 3, smallest kept 7
kept: 7 8 9

= newline. The output ends with a newline — print one after the last line.

Hints3 available
Topics:
Data Structures & AlgorithmsHeaps
1
Tab to indent (Esc then Tab to move on) · Ctrl+Enter to run · Shift+Alt+F to format · Ctrl+Space to expand shortcuts (p, fori)

Your Output

Run your code to see the output here...

Test Cases

Run your code to see test case results.