What is the difference between the binary-search-tree property and the min-heap property (see page 153)?

The min-heap property only describes the properties of right-children in a binary-search-tree. Left children are less than their parents.

Can the min-heap property be used to print out the keys of an \(n\)-node tree in sorted order in \(O(n)\) time? Show how, or explain why not.

No. The min-heap property implies no useful relationship between unrelated nodes. We would start with the root, which the min-heap property tells us is the smallest value in the entire heap. From there, the next smallest value is one of the root’s children, but we do not know which. Indeed, every time we find the next smallest value in sequence, two new nodes are added to the set of possible locations for the next value unless we are at a leaf. This expansion of possible locations that must be searched is proportional to the size of the heap which ensures that we cannot generate a sorted sequence in \(O(n)\) time.