PQ-Trees

Possibly the most irregular data structure we will cover is the PQ Tree. Firstly, the PQ tree was inspired by a baby’s mobile (in explaining this data structure to friends, I learned that many readers may be unfamiliar with typical American baby raising practices, pictured below is a mobile). Secondly, this model gives us a very efficient way to represent subsets of permutations, which can greatly help us solve combinatorial problems.

The PQ tree contains two types of nodes, P and Q (what a surprise). Conceptually, a P node is like a hook to hang ornaments on. The children of a P node may be permuted in any way. The Q node on the other hand, is like the horizontal bars pictured in the above baby toy. Its nodes are listed in order, but the bar itself may be rotated. The leaf nodes of a PQ tree are values, which can be reordered following the structure of the tree. The following are some examples of PQ trees, along with the set of permutations they represent.  

Applications:

So obviously, this data structure needs to help us solve a problem (the cool factor only gets it so far) and luckily it can have many interesting applications. Notice how we can use P and Q nodes to get sets of permutations that all have specific qualities. Look at the 3rd above example wherein we can generate 12 permutations on five items that all start and end with 1 and 5. Considering there are 120 permutations on five elements, PQ trees allow us to restrict our domain to a much more manageable size. This becomes more apparent as the number of elements increases to seven or eight (there are 5,040 permutations on seven elements and 40,320 permutations on eight).

So let’s consider a more practical problem, imagine we have a 2d array of 1’s and zeros. Our goal is to rearrange those rows such that on each row, all the 1’s are grouped together. This problem might sound arbitrary, but many scheduling tasks need to solve problems like this. Well, if there are N columns, then there are N factorial different permutations we would need to check. But we can do a lot better with PQ-Trees. 

The above animation shows how a PQ-Tree can be constructed which meets the requirements defined by the example matrix, one row at a time. Notice how at each iteration, columns which need to be next to each other are grouped together in a P node. Then, when more restrictions are incorporated, more structure is needed, and a Q node is used to make sure nodes stay adjacent where needed. Ultimately, this data structure takes our search space of 120 column permutations and discovers the set of four solutions.