Is there a good way to iterate through the maximum values of a BST with heap-like properties?

Is there a good way to iterate through the maximum values of a BST with heap-like properties?

Problem Description:

I am working with a tree of nodes organized as a sort of binary search tree for property 1 that maintains a max heap ordering for property 2, and I want to iterate through the maximum values for property 2.

My current solution involves making a copy of the tree, and then iteratively find a leaf, pop the current root, placing the leaf at the root of the tree, and down heaping that node to a suitable position, however this solutions seems overly complex and inefficient, so I was wondering whether there exists a simpler/faster way to achieve the same goal

Example Tree

Solution – 1

There is in general no efficient way to iterate over a max heap (or min heap) in sequential order.

For a max heap, we know that the largest item is at the root. The second largest will be one of the two children of the root. The third-largest could be a child of the root, or a grand-child of the root. And so on. The smallest item in a max heap can be any leaf node. Finding the xth item (by value) in a binary heap is an expensive operation.

The two most efficient ways to get the values of a binary heap in sequential order are:

1. Repeatedly do removeMax followed by re-adjusting the heap at each turn.
2. Make a copy of the heap and sort it.

Either way is O(n log n).