11.3. Complexity Analysis

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.

Heaps are a special kind of data structure that organizes elements in a hierarchical way, resembling a binary tree. This structure allows for efficient access to the smallest (or largest) element. The operations of inserting a new element and deleting the minimum element can both be executed in a logarithmic time complexity, denoted as O(log N). You can build a heap efficiently in linear time, O(N), by arranging elements bottom-up into a tree structure. Additionally, heaps can be represented as arrays, allowing for easy manipulation.

Think of a heap as a priority queue at an event. When people arrive (inserting elements), they take a position based on their priority (which is determined by their arrival time). If someone needs to be let in (deleted), the one with the highest priority (or lowest wait time) is allowed in first. Building this queue can be done efficiently, like organizing attendees from the back to the front to see who is waiting.

So, let us go back to Dijskstra's algorithm. So, 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.

Dijkstra's algorithm is a method used for finding the shortest path from a starting point (or initial vertex) to all other points in a weighted graph. It operates by initially assuming that all distances are infinite, except for the starting vertex, which is set to zero. As the algorithm proceeds, it explores the nearest vertex, updating the distances to its neighboring vertices based on the path lengths until all vertices have been visited.

Imagine you are trying to find the fastest route to deliver packages in a city. You start at your location (the initial vertex) and mark the distance to all nearby locations as infinite — except for your current location, which is zero. You then operate in a way similar to figuring out which delivery location is closest, updating your planned routes as you discover new paths — resembling how Dijkstra's algorithm systematically finds the shortest path.

So, the bottlenecks are first to find the j with the minimum distance, right. So, the naive implementation would take us order n time because we would have to scan all the unvisited vertices...

In Dijkstra's algorithm, one of the main challenges is efficiently selecting the next vertex to process, which has the currently minimum distance. A naive approach would involve checking each unvisited vertex, which could take linear time (O(n)). Instead, using a min heap allows for quickly retrieving the vertex with the minimum distance efficiently in logarithmic time (O(log N)). This modification significantly improves the algorithm’s performance.

Think about scheduling tasks based on urgency. If you don’t have a priority list, you might go through each task one by one to see which is the most urgent. But if you maintain a priority queue (like a min-heap), you could quickly see which task needs to be addressed next, allowing you to work more efficiently.

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...

When updating a value in a heap, it’s important to maintain the heap properties. If a value is increased (say from 12 to 44), the heap must be adjusted in a way that reflects this change. Essentially, the violation (where the parent is now larger than one of its children) must be corrected by moving the value upwards until no violations exist. Conversely, if a value is decreased, you might need to move it downward in the heap to maintain the structure.

Imagine a team of workers where each worker is ranked by their performance. If a worker’s performance rating increases, they should be moved up the rank; if it decreases, they should be moved down. Just like in a heap, you need to ensure that each worker is still in the correct position according to their performance compared to others.

So, we want to sort a list of values. So, what we can do is, we can first build a heap, right. So, we now start with some arbitrary sequence of values...

Heaps can also be used for sorting elements through a method known as heap sort. First, a maximum heap is built from the list of values, allowing for an efficient way to access the largest elements. By repeatedly removing the maximum element (delete max) from the heap and placing it in a sorted array, you can produce a sorted list in ascending order. Each delete operation takes logarithmic time, making the overall sorting process run in O(n log n) time complexity.

Consider sorting books on a shelf. If you place the heaviest (or highest priority) books at the top of the stack initially and remove them one by one (deleting the max), you're effectively organizing them in descending order. As you remove each book to place it in a designated spot, the next heaviest book will naturally position itself at the top — akin to how heaps sort data.

--