# 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?

Contents

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).

Rate this post
We use cookies in order to give you the best possible experience on our website. By continuing to use this site, you agree to our use of cookies.