Implicit Data Strucutres

A binomial queue is an irregular priority queue which takes advantage of binary trees to quickly order its elements. In short, its a queue of trees where each tree enforces a heap structure. I'll be writing a more in-depth article on Binomial Queues shortly. Until then, I recommend THIS LINK which has a wonderful visualization from the University of San Francisco. 

The following image shows a typical binomial queue with fifteen elements. Notice how to size of each tree follows the pattern 2 ^ n. 


Internally, this structure is held together with a series of pointers. The following image depicts that link structure. Notice how siblings are linked together, each having a pointer to their parent, but the parent only has a pointer to it's first child.


Wouldn't it be great if we didn't need to worry about all those links? Well with a little bit of work we can represent this whole structure implicitly! 

Lets look at a single binomial tree first. We know its structure contains sub trees that are also binomial trees. We know that the children of a binomial tree follow a 2 ^ n pattern, and the whole structure is recursive. We can use this information to our advantage. 

The following image depicts my binomial tree implicit structure:

We take the root of the tree and place it first in memory. Its children can be found at memory address 2^0, 2^1, and 2^3. To see the recursive structure, notice how node 4 at memory address 4 (this is a coincidence), can find its children at memory address 4+2^0 and 4+2^1. This next picture shows that independently. 


This pattern means that if we know the size of the array, we can recover the entire tree by following this pattern.

So how should we represent a whole binomial queue? 

Well, simply, if we were to "invent" a root node which connected all of the sub-tree roots, we could visualize the whole queue as a giant binomial tree! Yes, the best part of computer science remains the ability to use old solutions to new problems! 

Of course, sticking a dynamic data structure in an array will only increase the computational cost of its resizing operations (practically every binomial queue operation that is), but implicit structures are very important for storing and transferring data structures where users have limited memory and bandwidth. So it is important to see patterns in data structures and see how to take advantage of them.