Embercode: AI-powered software engineer course

1. A bounded heap keeps the k smallest values seen so far. Which heap does it use, and why?

A min-heap, because its front item is the smallest value kept so farA max-heap, because it keeps items in the order they were addedA max-heap, because its front item is the largest kept value, which is the one to remove when the heap holds more than k itemsA min-heap, because heappop always removes the largest value

2. Why does smallest_by_selection (the lesson version) call min(k, len(copy)) before its loop?

It stops the loop from reading an index past the end of the list when k is bigger than the listIt makes the result sorted from largest to smallestIt copies the list so the caller's list is not changedIt makes the heap keep exactly k items

3. What does this program print? ``

python
def smallest_by_selection(a, k):
    copy = list(a)
    limit = min(k, len(copy))
    for i in range(limit):
        best = i
        for j in range(i + 1, len(copy)):
            if copy[j] < copy[best]:
                best = j
        copy[i], copy[best] = copy[best], copy[i]
    return copy[:limit]

print(smallest_by_selection([10, 2, 8, 2, 7], 3))

``

[2, 7, 8][2, 2, 8][7, 8, 10][2, 2, 7]

4. What does this program print? ``

python
import heapq

wrong = []
for x in [3, 8, 5, 1, 7]:
    heapq.heappush(wrong, x)
    if len(wrong) > 2:
        heapq.heappop(wrong)
print(sorted(wrong))

``

[7, 8][1, 3][3, 8][5, 7]

5. A bounded heap handles n values and keeps at most k items. Roughly how many steps does it take in total?

n times log nn squaredn times log kn times k

Partial sorting