A Common-Sense Guide to Data Structures and Algorithms in JavaScript, Volume 1

Heap Properties

Now that you know what a heap is, let’s examine some of its interesting properties.

While the heap condition dictates that the heap be ordered a certain way, this ordering is still useless when it comes to searching for a value within the heap.

For example, let’s say that in the above heap, we want to search for the value 3. If we start at the root node of 100, should we search among its left or right descendants? In a binary search tree, we’d know that the 3 must be among the 100’s left descendants. In a heap, however, all we know is that the 3 has to be a descendant of the 100 and can’t be its ancestor. But we’d have no idea as to which child node to search next. Indeed, the 3 happens to be among the 100’s right descendants, ...