concept index in category algorithms

This is an excerpt from Manning's book Algorithms and Data Structures in Action MEAP V14. Login to get full access to this book.

It’s still high level, but clearer and more modular than the previous one.

Figure 2.4 A binary heap. Only priorities are shown for the nodes (elements are irrelevant here). In red, inside the small squares, you can the indices of the heap elements in the array.
Nodes are matched into array elements top-to-bottom, left-to-right.
Top: the tree representation for the heap. Notice how every parent is smaller (or at most equal) of its children and, in turn, all elements in its subtree.
Bottom: the same heap in its array representation.

To be clear, when we use a plain array we don’t have an efficient array’s method that tells us what’s the index of an element X, neither an efficient (as in sublinear) method telling us if an element is in the array or not. The only way we have to tell if an element is in the array is going through all the array’s elements – although in a sorted array we could use binary search to speed up the search.

(median, left, right) ← (-1, 1), [(-1.5,-2)], [(-1,6)]

copy