[simonask]

I think it's fairly useful. It means that you can convert a contiguous array to a heap with a fast O(n) read-only check instead of O(n log n) writes, so if you know that's the common case, you can detect it up front and only revert to normal binary heap insertion if it returns false.

[madars]

By the way, you can also construct heap in linear time - instead of doing n consecutive insertions, at least half of which require log n work, you can apply sift-down operations from bottom up, beginning with the last non-leaf node and working backwards to the root.

That way, roughly half the nodes are leaves (requiring no work), a quarter are at the second-to-last level (requiring at most 1 comparison/swap), an eighth at the third-to-last level (requiring at most 2 comparisons/swaps), and so on. Summing up 1 n/4 + 2 n/8 + ... gets you O(n) total complexity.

See https://en.wikipedia.org/wiki/Heapsort?useskin=monobook#Vari...

[gotoeleven]

I think the parent comment is asking what process or algorithm is there that would result in an array that was sometimes but not always a heap, and you'd want to do something based on whether the array was in fact a heap or not? Like in your example, what process do you have in mind that might result in a heap and might not?

[simonask]

Any time you deal with semi-trusted input, like an internal protocol or deserialization. :-)