Group Group Group Group Group Group Group Group Group

Heap Challenge 4 Solution bug

Hello,

In Heap Challenge 4 solution (check if a heap is a min heap), if we pass in elements = [6, 8, 11, 15, 12, 20], it will “out of range”

The book solution is on page 353

I believe we did not filter out the case below:
Parent start at element.count / 2 - 1
So right start at ( 2 * parent) + 2 = element.count
So elements[right] = elements[element.count] will be out of range !

So instead of if elements[right] < elements[i] { // 5
We can do if right < elements.count && elements[right] < elements[i] { // 5

Any comment ?

Thanks

1 Like

@jomoka Can you please help with this when you get a chance? Thank you - much appreciated! :]

Hi @oaranger sorry for the late reply. Yes this is a good catch, you are right. That should do the trick. We will make a note of this and fix it in the next edition of the book, much appreciated!

it will be same for left too yes?
if left < elements.count && elements[left] < elements[I]

Hi alif thanks for reading the book.

It will not be the same for the left side. As it will not be possible for an index out of bounds in this case.

If you take a look at the stride loop. It increments from 0 to half of the heap’s elements. As shown below:
stride(from: elements.count / 2 - 1, through: 0, by: -1)

Consider the case when you have one element in the heap. This loop will not even execute, and immediately returns true.

Let me know if you need more clarification! Thanks!