I created a standard min heap class. I am trying to figure out a way to index the values in the min heap in preorder traversal format. The only way I have seen it done is using left and right pointers. But the "nodes" in my array are not nodes just values. Is it possible to do preorder traversal on a min heap array using indexing? If so how?
The left/right links are implicitly available, as the left child of the value at index 𝑖 is to be found at index 2𝑖+1 (if within the size of the array), and the right child at index 2𝑖+2.
So you can just use the known preorder algorithm and use these formulas for visiting children.
For instance, we could have this min heap:
_3_
/ \
6 4
/ \ /
10 9 5
...which would be encoded in an array as follows:
[3, 6, 4, 10, 9, 5]
The preorder traversal would be:
3 6 10 9 4 5
Here is an implementation in JavaScript that is run for this example:
function preorder(minheap, start) {
if (start >= minheap.length) return; // all done
console.log(minheap[start]);
preorder(minheap, start * 2 + 1); // left child
preorder(minheap, start * 2 + 2); // right child
}
// Example run:
const minheap = [3, 6, 4, 10, 9, 5];
preorder(minheap, 0);