Beautifully explained. I have seen maybe 5 other videos with fancy animations but they all lacked clear explanation of why the inverse look up was needed. Thank you for this, it was super helpful!
Hi, nice videos. However, I'm confused at 11:10 . How does this new 3 array representation imply that contains() method takes O(1) time? If I want to check if the heap contains value 309, I don't have a direct pointer anymore, I would have to traverse "values" array and check if 309 is present there, which makes it O(n) not O(1);
You are right. The only time that holds is in the examples prior to the key/value pairing. The position map would only work on keys and not values, and values are stuck at a O(n) lookup time
So with the 3 array representation, when you heapify (sink, swim), do you change the values array or the heap and position maps arrays? because heapifying the values array would still automatically make the heap array maintain the heap property correct? But then the values for the heap array is just its indices and wouldnt be useful at all right ?
Beautifully explained. I have seen maybe 5 other videos with fancy animations but they all lacked clear explanation of why the inverse look up was needed. Thank you for this, it was super helpful!
Hi, nice videos. However, I'm confused at 11:10 . How does this new 3 array representation imply that contains() method takes O(1) time? If I want to check if the heap contains value 309, I don't have a direct pointer anymore, I would have to traverse "values" array and check if 309 is present there, which makes it O(n) not O(1);
You are right. The only time that holds is in the examples prior to the key/value pairing. The position map would only work on keys and not values, and values are stuck at a O(n) lookup time
So with the 3 array representation, when you heapify (sink, swim), do you change the values array or the heap and position maps arrays? because heapifying the values array would still automatically make the heap array maintain the heap property correct? But then the values for the heap array is just its indices and wouldnt be useful at all right ?
11:40 isn't this just a roundabout to using a hashmap for the positions?