Traversing a complete binary min heap

Question 1

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

Question 2

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.

Remove items one at a time in sorted order to "visit" them for the traversal.
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).
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.

Question 3

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.

Question 4

You can use std::set, if you're ok without duplicates. A std::set iterator will traverse in order and maintains ordering based on the default comparator. In the case of int, it's <, but if you traverse in reverse order with rbegin(), you can traverse from highest to lowest. Or you can add a custom comparator. The former is presented:

#include <iostream>
#include <vector>
#include <set>

using namespace std;

int main() {

  vector<int> data{ 5, 2, 1, 9, 10, 3, 4, 7, 6, 8 };

  set<int> ordered;
  for (auto n : data) {
    ordered.insert(n);

    // print in order
    for (auto it = ordered.rbegin(); it != ordered.rend(); it++) {
      cout << *it << " ";
    }
    cout << endl;
  }

  return 0;
}

Output:
5 
5 2 
5 2 1 
9 5 2 1 
10 9 5 2 1 
10 9 5 3 2 1 
10 9 5 4 3 2 1 
10 9 7 5 4 3 2 1 
10 9 7 6 5 4 3 2 1 
10 9 8 7 6 5 4 3 2 1