You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
The current Heap._checkInvariants method doesn't fully validate the min-max invariants -- it just checks to see if the property holds for the immediate children of any node.
Instead, we should compare the value stored in every node with a currently expected range of values.
E.g., in the tree below, when checking descendants of 11, each value needs to be within the range 11 ... 41. Each new level narrows this range a bit further (by refining the lower or upper bounds, depending on the polarity of the node).
Implementing this would mean that we'd have to keep track of a stack of expected ranges in addition to their associated indices. (Or switch to a recursive implementation.)
The text was updated successfully, but these errors were encountered:
Actually, I misread the original implementation -- it did verify the full min-max property, it was just doing it slower than necessary, by iterating over each node's entire subtree, rather than visiting each node exactly once.
The current
Heap._checkInvariants
method doesn't fully validate the min-max invariants -- it just checks to see if the property holds for the immediate children of any node.Instead, we should compare the value stored in every node with a currently expected range of values.
E.g., in the tree below, when checking descendants of 11, each value needs to be within the range 11 ... 41. Each new level narrows this range a bit further (by refining the lower or upper bounds, depending on the polarity of the node).
Implementing this would mean that we'd have to keep track of a stack of expected ranges in addition to their associated indices. (Or switch to a recursive implementation.)
The text was updated successfully, but these errors were encountered: