11.2.2. Updating Heap Values

So, we need to update the distance, that is, we need to get into the heap and change values, so we need to update heap values. Now, we have not really seen how to update heap values, we have only seen insert and delete min and delete max. So how does update work, right.

In a heap, it is crucial to update values efficiently, especially when we have to adjust distances, such as in Dijkstra's algorithm. While we are familiar with inserting and removing elements from the heap, updating an existing value is a new challenge. This section emphasizes the importance of being able to modify values within the heap to maintain its properties and ensures we can continue efficient operations.

Think of a priority list where tasks are ranked by importance. If a new task comes in that is more important than an existing one, you must update the ranking of the current tasks instead of starting from scratch. Updating the ranking ensures that your tasks remain organized without having to rewrite the entire list.

So, supposing we want to change this value from 12 to 44, right. If we increase this value, then with respect to its children it cannot get any smaller, right. So, if 12 is bigger than 10 and 11, any larger value will also be bigger than 10 and 11.

When increasing a value in a heap, you don't need to check down the tree since the new value will naturally be greater than its children. However, since you have increased the value, it may now be larger than its parent, which causes a heap violation. To correct this, you must compare the new value with its parent and potentially swap them if the new value is larger, continuing this process upwards until the heap property is restored.

Imagine you're playing a game where your rank is based on points. If you score more points and that new score puts you above your previous rank, you'll have to move up in the leaderboard. Similarly, in a heap, when you increase a value, it must be repositioned to maintain its order, just like you would move up the leaderboard when your score increases.

The other type of change is to decrease the value. So, supposing I take this 33 and I make it 9. Now, again by the same logic it was 33, was smaller than 44, 9 will also be smaller than 44. Any value smaller than 33 cannot create a violation up.

When decreasing a value in the heap, the new value must still be smaller than its parent. As such, you need to check its children to ensure the heap property is maintained. This involves swapping the decreased value with its larger child until it percolates down to its proper location. This updating process of adjusting downwards restores the heap property because smaller values will not violate the relationships established in the heap structure.

Think of it like managing a team of players based on performance scores. If a player underperforms, their score drops. They might have to take a step back to allow others to come forward based on their scores. Just like in a heap, when the score decreases, the player must move down in the lineup to maintain an accurate ranking.

So, what our previous example showed up is, if we put our finger on the node in the heap and change its value, we know how to adjust the heap. But how do we find where j is in the heap, right?

To successfully update a value in the heap, one must first locate the position of that value. This is crucial, especially in algorithms like Dijkstra's where dynamic updates are frequent. Therefore, we utilize auxiliary arrays to maintain a mapping between the graph's vertices and their corresponding positions in the heap. This dual indexing allows us to efficiently find and update the right node in the heap whenever required.

Imagine navigating through a library where books (vertices) are organized on shelves (the heap). To find a specific book and update its details, you first need to know where that book is located. If you have a library catalog (the auxiliary array), you can quickly locate the book on the shelf (the heap) and make necessary updates without searching through every shelf.

So, when I do this, I need to go down to its two children in the heap and recognize that this 24 must change. Now, since 24 must change, I must know also how to update it.

Whenever a value in the heap is swapped, it's essential to update the auxiliary data structures as well to reflect the changes regarding which graph vertices correspond to which heap nodes. This means that each time we make adjustments in the heap due to an updated value, we also need to ensure that our auxiliary indices account for these changes to maintain a reliable link between our graph structure and the heap representation.

Consider a seating arrangement for a concert where each seat has a number (index). If someone changes their seat, it's not just the seating arrangement that has to be updated; the event organizer must also update a master list that details who is sitting where. This ensures that everyone knows the current seating plan without confusion, similar to how we update indices in our heap consistently.

--