CJCoding With Joseph
15free / daySign inCreate account

Find the k-th Smallest Value Without Changing the Heap

Write min_heap_kth_smallest. It hands back the k-th smallest value through the pointer value (k = 1 is the smallest, k = 2 the second smallest, and so on) and returns true. It returns false when there is no such value. The heap must look exactly the same afterwards.

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.

A heap only knows where its SMALLEST value is. The second, third or fifth smallest could be in many places, so there is no index to jump to. But removing gives values in order: the k-th value you remove is the k-th smallest. Removing would wreck the caller's heap, so do it on a COPY, and destroy the copy when you are done.

k = 3 on the heap 1 4 2 7 5:

  the caller's heap           a copy (thrown away afterwards)

        1                     remove -> 1     (1st smallest)
       / \                    remove -> 2     (2nd smallest)
      4   2                   remove -> 4     (3rd smallest)  <- the answer
     / \
    7   5                     destroy the copy

  untouched: 1 4 2 7 5

min_heap_copy, min_heap_remove and min_heap_destroy are already written.

Requirements: 1. When k is less than 1 or more than count, return false and leave *value alone. 2. Otherwise make a copy of the heap and remove from the copy k times. The last value removed is the answer: it goes in *value. 3. Destroy the copy, then return true. 4. Do not change source.

Do NOT write a main function.

Expected Output:

k = 1: 1
k = 4: 4
k = 7: 7
heap afterwards: [1, 4, 2, 7, 5, 3, 6]

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

Hints4 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.