I'm reading the book "Cracking the Coding Interview: 6th Edition" and I'm confused on their definition of "min-heaps" and how they say "Extract Minimum Element" works.

The way they say that Extract Minimum Element is implemented is as follows:

First, we remove the minimum element and swap it with the last element in the heap (the bottommost, rightmost element). Then, we bubble down this element, swapping it with one of its children until the min-heap property is restored.

Do we swap it with the left child or the right child? That depends on their values. There's no inherent ordering between the left and right elements, but you'll need to take the smaller one in order to maintain the min-heap ordering.

This algorithm will also take O(log n) time.

Then they show the following diagram describing how min-heap's "Extract Minimum Element" method would work:

My questions are as follows:

1. In the example shown in the image above, how is 80 the "bottommost, rightmost" element of the min-heap prior to when we ran the "extract minimum element" method? It couldn't have been below 88, right, because 88 is greater than 80? Is this just a mistake made by the book?
2. How is this algorithm O(log n) time? I would think that it would take O(n) time in order to find the bottommost, rightmost element of the min-heap, as in the worst case scenario, we'd need to search through every node to find a node which doesn't have a sibling on the right (or if the all leaf nodes are at the same level and that level has the maximum number of nodes). Do we maintain a reference to the min-heap's rightmost, bottommost element or something within the heap, so that we can access it more easily?

CodePudding user response：

1. You're correct, 80 should not have been in the dashed circle position to start because it is less than its parent. This violates the basic requirement for a min heap that the value at each node is equal to the minimum of all values stored in the subtree having that node as root. This is an error in the text. If you change the 88 to a 78 (for example), then the heap starts off correctly and ends up correctly.

2. In practice, heaps are generally stored in an array. The array indices are found by filling each level of the tree from left to right, and moving to the next level once the bottom-most level gets filled. If we start with the root corresponding to index 1, the second level of the tree has indices 2 and 3; the third level of the tree has indices 4, 5, 6, and 7; and so on. Using this scheme, the bottom rightmost element of the heap (viewed as a tree) is found at the index corresponding to the count of how many elements are currently stored in the tree, the children of node k are found at indices 2k and 2k 1, and the parent of node k is at index floor(k/2) for all k > 1. Consequently, all of the navigation required involves array access with easily calculated indices, i.e., constant time operations. The overall complexity is determined by the conceptual depth of the tree, which is O(log(N)) when the heap contains N items.