10.3. Heap Representation

So, every time we do an insert, we start at a leaf node that we create and we walk up to the root. The worst-case height of the tree is important because it dictates the complexity of the operation. The height of a tree is defined as the longest path from the root to a leaf, which can be counted in terms of either edges or vertices. In a binary tree, for level 0, we have 2^0 nodes (1 node), for level 1, we have at most 2^1 nodes (2 nodes), and this continues, doubling at each level. Thus, the number of nodes at level i is given by 2^i, and if there are k levels, it sums to 2^0 + 2^1 + ... + 2^(k-1) which equals 2^k - 1. This means that if we have N nodes, the height of the tree will be log(N), making insertions take time O(log N).

In a heap, when we insert a new element, we always start at a leaf node. The height of the heap determines how long it will take to perform operations like insertion. The height is defined as the longest path from the root to any leaf node. In a binary heap, as you go down each level, the number of nodes doubles. So if you have k levels, the number of nodes follows a formula that leads us to conclude that the height of the heap is logarithmic relative to the number of nodes (N). Therefore, performing insertions in a heap will take time proportional to log(N).

Think of a company hierarchy where the CEO is at the top (root) and each level down has more employees (leaf nodes). As you go down the levels, the number of employees doubles. If you want to get approval from the CEO (insert a new idea), you need to climb up through the hierarchy, which could take longer if there are many levels, illustrating how the height impacts efficiency.

The other operation that we need to implement for a priority queue is to delete the maximum. The maximum in a max heap is always at the root. When we remove this maximum, we’re left with a node that doesn’t belong at the root anymore. To maintain the structure, we replace the root with the last leaf in the heap, which disrupts the heap property. To fix this, we need to check the children of the new root and swap it with the larger child if it is smaller, repeating this process downwards until we restore the heap property. The time complexity for deleting the maximum follows the same principles as insertion: O(log N).

When we want to delete the maximum element (the root) from a max heap, we need to fill the gap left by this operation. We replace the root with the last leaf node and then check if this new root satisfies the heap property. Because it might not (as it could be smaller than its children), we compare it with its children and swap it with the larger child. This continues down the heap until the heap property is restored. Since the height of the heap is logarithmic concerning the number of nodes, this operation also takes O(log N) time.

Imagine a line of people waiting to get on a bus, where the person with the highest priority (the maximum) is at the front. If that person leaves the line, the last person in the queue (the last leaf) steps up to the front. However, this person might not have the same priority. So, they check who is actually waiting behind them and keep swapping places until the most important person is again at the front, illustrating the process of restoring order.

Heaps can be efficiently implemented using arrays. We can number the nodes starting from the root as 0, then the first child as 1, and so forth. For any node in position i, its children are located at positions 2i + 1 and 2i + 2. Conversely, to find a parent node from a child at position j, we can use the formula floor((j - 1) / 2). This way, all operations involving traversing the heap can be performed using just the indexes of the array without needing additional pointers.

In a heap, we can represent it as an array instead of a more complex datastructure. Each node is given a position in the array, where the root is at index 0, and the children of a node at position i are at positions 2i + 1 and 2i + 2. This allows us to easily calculate where the children and parents are without needing links between nodes. Since arrays are contiguous blocks of memory, this makes traversal and manipulation simpler and faster.

Think of a stack of trays in a cafeteria. Each tray represents a node (or a person in our previous analogy). The way trays are stacked closely together allows you to easily find a tray (index) at the top. If you want to know which trays are underneath (children), you can quickly calculate their positions without having to search through a bunch of trays or look in multiple places.

To build a heap from a given set of values, a naive approach involves inserting each element one by one into the heap, which would take O(N log N) time. However, there's a more efficient method called bottom-up heapification. By viewing the array as a complete tree and fixing nodes starting from the bottom, where the leaves automatically satisfy the heap property, we can do this in O(N) time. Essentially, we only need to fix the non-leaf nodes, which halves the number of nodes that need adjustment as we go up each level.

Instead of inserting elements individually into the heap and costing log N time for each element, we can take a more efficient approach known as bottom-up heapification. During this process, we treat the entire array as a complete binary tree and start fixing from the last non-leaf node upwards. By only fixing these nodes, our adjustments become significantly fewer and much more efficient, allowing us to construct a heap in linear time O(N).

Consider building a pyramid of blocks. If you start with the bottom layer of blocks already laid out (the leaves), you only have to focus on adding blocks on top in a systematic way, fixing the alignment as you go higher rather than building from the top. This allows you to build the pyramid much faster compared to starting from the top and trying to balance everything as you go.

--