11.1. Design and Analysis of Algorithms

To complete our discussion of heaps we will see how to use heaps and Dijskstra’s algorithm, and also how to use heaps for a different type of sorting. So, remember that heaps are a tree implementation of priority queues in which insert and delete or both of complexity log N. You can build a heap bottom up in order N time and you can represent it as a tree. And so you can manipulate it in a, I am sorry, you can represent a tree in an array, so you can manipulate it very easily.

A heap is a specialized tree-based structure that satisfies the heap property, where the parent node is always greater than (or equal to) its child nodes. This makes heaps useful for implementing priority queues, where you need to efficiently retrieve the highest (or lowest) priority element. Inserting an element into a heap takes logarithmic time, O(log N), which is efficient due to the height of the tree being log N. Additionally, heaps can be constructed from an unordered list in linear time, O(N), by building it bottom up. They are often represented using arrays, which allows for simpler manipulation of tree operations.

Think of a heap as a hierarchy in a company where the CEO (the root) has the highest authority and managers below have lesser authority. Just as it’s easier to manage a company from the top down, heaps allow us to efficiently access the highest priority item at the top.

So, let us go back to Dijskstra's algorithm. In Dijskstra's algorithm, we start with the initial vertex and we keep burning these vertices, right, so we keep visiting vertices according to their distance. So, initially we set the distance to be infinity for everything, right. And we use the starting point as, setting the distance to the start vertex as 0, and then we find the smallest unvisited vertex, set it to be visited and recompute the distance of each of its neighbours.

Dijkstra’s algorithm is a popular method for finding the shortest paths between nodes in a graph. It initializes distances from the starting node to all other nodes as infinity, except for the starting node itself, which is set to zero. The algorithm then explores the nearest unvisited vertex, updating the distances of its neighboring vertices. This process of selecting the vertex with the smallest distance and updating its neighbors continues iteratively until all vertices are visited.

Imagine navigating through a city where each intersection is a location (vertex) connected by roads (edges). Dijkstra’s algorithm allows you to chart a path from your home (starting vertex) to various destinations by keeping track of the shortest driving distances, initially assuming that it's infinitely far to each destination until you explore the routes.

What seems obvious from what we have discussed so far is that we should maintain distance as a heap and use delete min in this case, because we will want a min heap. The bottleneck here is that 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.

To efficiently implement Dijkstra’s algorithm, we use a min-heap to always retrieve the vertex with the smallest distance quickly. Whenever we update the distance of a vertex, we must modify the value in the heap. This operation typically involves removing the old value and inserting the new value, or 'bubbling down' the modified value to restore the heap property. This is crucial for maintaining the efficiency of the algorithm.

Think of a prioritized task list where you always want to tackle the easiest or quickest task first. If you manage to complete a task faster than you expected, you would need to update your list to reflect your new priorities, ensuring the simplest task remains at the top for quick access.

If we replace, 24, 12 by 44, then we find that there is the heap violation above. So, now, we treat this exactly like we did insert. We look at the parent and so on. So, we fix this violation upwards... Similarly, if 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.

When updating a value in a heap, there are two scenarios: increasing a value or decreasing a value. If we increase a value, we may need to move it up the heap to maintain the heap properties. Conversely, if we decrease a value, we often need to move it down to ensure that the smaller value doesn’t disturb the ordering with respect to its parent. The method of fixing heap violations depends on whether the value changes upwards or downwards in the structure.

Consider a stack of papers organized by size. If you pull out a large paper and replace it with a smaller one, you must ensure that smaller papers are still at the bottom. Conversely, if you replace a small paper with a larger one, it should be moved up in the stack to maintain the order.

So, we need this extra information to be kept separately, right. So, we would keep two new arrays pointing from the nodes... to indicate that we have an array, saying that the node represents the distance of vertex 8 and to indicate that we have an array.

To efficiently update values in the heap, it’s crucial to maintain a mapping between the vertices and their positions in the heap. By using two arrays, one for vertices and one for heap indices, we can quickly locate where a particular vertex is within the heap. This mapping allows the algorithm to perform updates without needing to traverse the heap for the vertex’s position each time.

Think of this as having a set of student ID cards (vertices) and a seating chart (heap). If a student moves to a new seat, you can quickly update both the card and chart without having to search through them each time, ensuring their current position is always known.

So, before we leave heaps, let us see how to use heaps to sort. So, we want to sort a list of values. So, what we can do is, we can first build a heap... extracting elements from the tree in descending order.

Heap sorting involves building a heap from a given list and then repeatedly removing the maximum (or minimum, depending on heap type) element from the heap. Each removal restructures the heap, allowing the next maximum/minimum to be accessed easily. Because each extraction is O(log N), and building the heap is O(N), the overall time complexity for heap sort ends up being O(N log N).

Imagine sorting a pile of laundry by size. First, you organize them in a way where the largest items are easiest to access (like building a heap). Each time you take the largest item out, the next largest moves up to take its place, ensuring the order remains intact as you sort through the pile.

--