Traversing a complete binary min heap

Question

I am not sure how to traverse the tree structure below so that the nodes are always in ascending order. Heapifying the array [9 8 7 6 5 4 3 2 1 0] results in the array [0 1 3 2 5 4 7 9 6 8] which I think corresponds to this representation:

Wanting to keep the array as is (because I want to do efficient inserts later) how can I efficiently traverse it in ascending order? (That is visiting the nodes in this order [0 1 2 3 4 5 6 7 8 9])

Answer 1

You can't traverse the heap in the same sense that you can traverse a BST. @Dukeling is right about the BST being a better choice if sorted traversal is an important operation. However you can use the following algorithm, which requires O(1) additional space.

Assume you have the heap in the usual array form.

1. Remove items one at a time in sorted order to "visit" them for the traversal.
2. After visiting the i'th item, put it back in the heap array at location n-i, which is currently unused by the heap (assuming zero-based array indices).
3. After traversal reverse the array to create a new heap.

Removing the items requires O(n log n) time. Reversing is another O(n).

If you don't need to traverse all the way, you can stop at any time and "fix up" the array by running the O(n) heapify operation. See pseudocode here for example.

Answer 2

I would actually rather suggest a self-balancing binary search tree (BST) here:

A binary search tree (BST) ... is a node-based binary tree data structure which has the following properties:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• The left and right subtree each must also be a binary search tree.
• There must be no duplicate nodes.

It's simpler and more space efficient to traverse a BST in sorted order (a so-called in-order traversal) than doing so with a heap.

A BST would support O(log n) inserts, and O(n) traversal.

If you're doing tons of inserts before you do a traversal again, it might be more efficient to just sort it into an array before traversing - the related running times would be O(1) for inserts and O(n log n) to get the sorted order - the exact point this option becomes more efficient than using a BST will need to be benchmarked.

---

For the sake of curiosity, here's how you traverse a heap in sorted order (if you, you know, don't want to just keep removing the minimum from the heap until it's empty, which is probably simpler option, since removing the minimum is a standard operation of a heap).

From the properties of a heap, there's nothing stopping some element to be in the left subtree, the element following it in the right, the one after in the left again, etc. - this means that you can't just completely finish the left subtree and then start on the right - you may need to keep a lot of the heap in memory as you're doing this.

The main idea is based on the fact that an element is always smaller than both its children.

Based on this, we could construct the following algorithm:

• Create a heap (another one)
• Insert the root of the original heap into the new heap
• While the new heap has elements:
  • Remove minimum from the heap
  • Output that element
  • Add the children of that element in the original heap, if it has any, to the new heap

This takes O(n log n) time and O(n) space (for reference, the BST traversal takes O(log n) space), not to mention the added code complexity.

Answer 3

Just sort the array. It will still be a min-heap afterward, and no other algorithm is asymptotically more efficient.