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

Purl

If you want a sorted list, then a heap is not the proper data structure. There are many data structures that will efficiently maintain a sorted list. I've had very good luck with skip lists. – Spinal

Can skip lists use contiguous memory? – Purl

You can build a skip list in an array, but it's messy. I think I see your problem. You want an implicitly ordered data structure like a binary heap, but that you can efficiently traverse in ascending order (i.e. sequentially). If such a thing exists, I don't know about it. – Spinal

Answer 1

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

Undeceive

Will I have to sort it every time I want to traverse it? because then there's no point in having a heap I guess – Purl

@Purl That's a more interesting question because there will be some order to exploit. I would suggest a smart sorting algorithm that detects runs (e.g., timsort) and has an O(n)-time best case. – Undeceive

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

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.

Interleaf

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

Hobo

Do you know of any implementation of a BST that uses contiguous memory? – Purl

You could use a similar representation as the one you did for a heap, where you use an array and the root is at the 1st index (1-indexed for simplicity) and the left and right children of a node at any given index i is at 2i and 2i+1 respectively. I'm not aware of any libraries doing this, possibly because the cost of resizing is substantial. – Hobo

Answer 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 

Homan

It looks like a nice solution too, thanks! Do you know of any good workarounds for allowing duplicates? – Purl