11.2.3. Handling Value Changes

Supposing we want to change this value from 12 to 44. If we increase this value, then with respect to its children it cannot get any smaller. So, if 12 is bigger than 10 and 11, any larger value will also be bigger than 10 and 11. So, we make it 44. We do not have to look down, but because we make it bigger, it can become bigger than its parent.

When you want to increase a value in a heap, like changing 12 to 44, you first notice that the new value (44) is bigger than its children (10 and 11). Since heaps maintain a structural property where a parent is smaller than its children, you don't need to check the children after the increase. However, you must check if it is now larger than its parent. If it is, you need to 'fix' this by moving it upwards through the heap until the heap property is restored. You do this by repeatedly swapping the node with its parent until there are no more violations of the heap's rules or you reach the root.

Imagine you are stacking boxes where each box can hold another smaller box. If you add a larger box on top of a smaller box, it may not stay balanced. You would need to move the larger box up, swapping it with the boxes below until it is correctly positioned on top of the largest box it can balance over.

The other type of change is to decrease the value. Supposing I take this 33 and I make it 9. By the same logic, since 9 will still be smaller than its parent (33), I have to check it against its children.

When decreasing a value in a heap, like changing 33 to 9, the new value is still smaller than its parent, which means the heap property isn't violated upwards (it will still be less than its parent). Here, the potential issue arises with its children. You must check if the new value (9) is smaller than its children (in this example, 24 and 11). If it is, you need to move the new value downwards in the heap. You do this by swapping it with the larger of its children until the heap property is maintained.

Think of a game where players are climbing a staircase to reach the top. If a player falls and starts climbing again from a lower step, they will check if they can step on lower stairs (their children) without being left behind. If they step on a lower stair, they’d climb down to make sure they are helping more players reach the step above them rather than blocking them.

For Dijkstra’s algorithm, we take a vertex j and say, update this distance. If we change its value, we can adjust the heap accordingly. However, the challenge is to identify where j is located in the heap, and we need two new arrays to track these locations.

In Dijkstra's Algorithm, when you want to update a vertex's distance that is represented in the heap, you need to find its exact location in the heap structure first. Since the value can change, we cannot simply refer to it by its vertex number. To facilitate the process, we maintain two arrays: one mapping vertices to their positions in the heap and another mapping heap positions back to their vertices. This way, when you find a vertex and want to change its value, you can do so efficiently and ensure that the heap remains valid after the change.

Consider a classroom where students (vertices) are seated in a specific order (the heap). If a student suddenly moves to a new position because they need to give a presentation (updating), the teacher needs to note both the old and new seating arrangements (two arrays) so everyone can find the right path to their new seats without confusion.

--