11.4.1. Building and Maintaining a Heap

Heaps are a tree implementation of priority queues in which insert and delete operations have a complexity of log N. You can build a heap bottom up in O(N) time and represent it as a tree, which can be easily manipulated in an array.

A heap is a special kind of binary tree that satisfies the heap property, which dictates that in a max-heap, for any given node, the value of that node is greater than or equal to the values of its children. This allows for efficient access to the maximum element. The process of building a heap from an arbitrary list of elements can be done in linear time (O(N)), and once it's built, we can insert and delete elements quickly (O(log N)). Heaps are often stored in arrays, where the children of the node at index i are found at indices 2i+1 and 2i+2. This array representation is beneficial since it allows for efficient traversal without needing pointers.

Imagine storing books in a library. If you want to quickly find the most important books (highest priority), you could think of organizing them in a stack (heap). When you add a new book, you just place it carefully (insert). However, if you want to access the most important book, you simply pick the top one (delete). If you have to find its position, you could scan through the stack quickly because they are all neatly organized.

When updating values in a heap, increasing a value may cause a violation upwards. We have to check and possibly swap it with its parent until no violations remain. Conversely, decreasing a value requires checking and possibly swapping it downwards with its larger children.

When you change the value of a node in a heap, the structure's properties might get violated. If you increase a value, that node can become larger than its parent, leading to a violation that must be resolved by moving the node upward in the tree until the heap property is restored. If you decrease a value, it might become smaller than its children, necessitating a downward adjustment in which you swap the node with the largest child until the heap property is satisfied again.

Consider a ladder made of boxes. When you want to increase the height of a box, you need to move it up until it finds its proper place in the stack (upward adjustment). But if you decide to lower a box's height, it might sink below some other boxes around it, so you need to lift it up again to ensure that no box is above it (downward adjustment).

In Dijkstra's algorithm, when we need to update the distance of a vertex represented in a heap, we must know its location in the heap. This requires maintaining additional arrays that map vertices to their corresponding positions in the heap.

Dijkstra's algorithm uses a heap to keep track of the shortest paths to each vertex in a graph. When a vertex's distance needs to be updated, we have to find where that vertex is located in the heap, which can be efficiently managed by using two additional arrays: one that maps graph vertices to heap indices and another that performs the reverse mapping. This way, when we do any swap in the heap due to updates, we can also update these mappings accordingly to maintain consistency.

Think of managing a game with characters (vertices) that can change positions on a leaderboard (heap). To update a character's score, you need to know exactly where that character is in the leaderboard. By keeping a list that tells you each character's rank and another that tells you their position on the leaderboard, you can easily find a character and adjust their position when their score changes (updating the heap).

To sort a list of values, you can first build a heap and then repeatedly extract the maximum (or minimum) to get the desired order. This results in an O(N log N) sorting process.

Heap sort works by first turning the input list into a heap – a binary tree structure that allows for efficient maximum (or minimum) extraction. Once the heap is constructed, you can remove the largest item (for max heaps) and place it in sorted order. Each extraction requires rearranging the heap, which can be done in logarithmic time. Thus, if you repeat this process for all elements, the overall time complexity of heap sort is O(N log N), where N is the number of elements to sort.

Imagine sorting playing cards where you want to put them in order. First, you build a stack that can easily provide you with the highest card. After confirming it's the highest, you put it aside in a separate pile and then repeat the process with the remaining cards until they're all sorted. Each time you pick a card, you strategically place it in the correct order, ensuring everything is sorted at the end.

--