Tournament Trees and Binary Heaps

Akshat Chaturvedi
Last Updated: May 13, 2022

What is a Tournament Tree?

As the name suggests, a tournament tree comes from the idea of a tournament or a competition. If there are p players in a tournament, then the tournament tree will have p leaf nodes which can also be called external nodes, and it’ll have p-1 internal nodes. The tournament trees are also known as selection trees.

 

The tournament tree is an application of the heap data structure. It is a binary heap; hence the tournament tree is also a complete binary tree and satisfies the heap-order property.

 

There are two types of tournament trees:

  1. Winner Trees
  2. Looser Trees

Winner Trees

The idea here is that in a winner tree, the nodes at a particular level store the winner of the two nodes at the level below it. Hence, the tree’s root node stores the overall winner of the competition.

 

For instance, if we consider that in a tournament there are a total of eight players (1, 2, 3, 4, 5, 6, 7, 8) and in a match between any two players among these, the player with numerically smaller value wins the match (minimum winner tree).

 

 

The winner tournament tree constructed for the above example will look like this.

 

Clearly, 1 is the winner here because it is the numerically smallest element in the group.

 

If we observe the tree, we’ll see that it is a min-heap because, along with being a complete binary tree, the value of each node is lesser than or equal to the value of its children.

 

Note: A tournament tree will always be a heap, but a heap is not always a tournament tree because, in a tournament tree, the value of each node must be the value of its left or right child, but in a heap, a node can have any value lesser than it’s left and right child.

Looser Trees

The loser tree is another type of tournament tree in which the nodes at a particular level store the loser of the two nodes at the level below it. In a Looser tree, the tournament’s winner is stored at the top, and the second place (runner-up) is the child of it.

 

So, if we are considering a numerically smaller value as the winner, then each node’s value in a Looser Tree will be the greater value among both of its children.

 

 

The loser tree constructed for our example will look like this.

 

One advantage of looser trees compared to winner trees is that it is sufficient to examine the nodes on the path from leaf nodes to the root node for restructuring the tree in looser trees.

 

For each of the matches, the time complexity is O(1), and in total, there are n-1 nodes (internal nodes); hence the time complexity to initialize the tree is O(n).

Finding Median of the Sorted Arrays (Tournament Trees Approach)

 

One of the Tournament Trees applications is that we can find the median of N sorted arrays. For instance, if we have N ascending order sorted arrays, we can efficiently use minimum winner tournament trees to find the median.

 

The arrays will act as players (leaf nodes of the tournament tree), and the winner element from respective arrays will occupy the internal nodes.

Demonstration

 

Assume that we have 3 sorted arrays of different sizes:

Array 1 = {2, 5, 7, 11, 15},

Array 2 = {1, 3, 4}, and

Array 3 = {6, 8, 12, 13, 14}

 

The respective sizes of arrays are 5, 3, and 5; hence the median will be the 7th element of the overall array.

 

Sorted merged array = {1, 2, 3, 4, 5, 6, 7, 8, 11, 12, 13, 14, 15}

 

Median = 7th element = 7

 

Let’s solve this using winner tournament trees.

 

Initially, the leaf node will contain the first element of the respective sorted arrays. Since there are three arrays, we’ll assume that the fourth leaf node is either null or contains some very large value (9999999).

 

Here 1 is the winner, so we replace the leaf node with the next value from the respective array. (i.e., node 3 will replace node 1)

 

Now, 2 is replaced by 5. These steps will continue till we get the 7th element from the tournament tree.

 

 

Now since array 2 is empty, 4 will be replaced with a very large value 9999999.

 

 

Finally, after the 7th iteration, we will get our median which is 7.

 

The time required to merge N sorted arrays of size M (assuming all arrays have the same size) is O(M*logN), and the time required to find the median will be O(m*logN), m being the median position (7 in our above example).

Frequently Asked Questions

What is the Truck Loading Problem?

Answer: The Truck Loading problem is an application of tournament trees. In this problem, ‘n’ packages have to be loaded into the trucks, and each of the n packages has some weight. We have to minimize the number of trucks, given that a truck has a maximum capacity of ‘t’ tons.

 

What are Heaps?

Answer: A Heap data structure is a special binary tree that meets two conditions, namely CBT and Heap-order property.

Complete Binary Tree - All levels except the last level are completely filled in a CBT, and we fill the last level from left to right.

Heap-order property - According to the heap-order property for a Min Heap, the value of each node should be less than or equal to the value of its child nodes, and the minimum element should always be at the top of the tree.

 

What is a complete binary tree?

Answer: A complete binary tree is a special type of binary tree in which all levels except the last level are filled completely, and the last level is filled from left to right.

 

What are the use-cases of the tournament trees?

Answer: The applicabilities of the tournament trees are:


We widely use Tournament Trees for external sorting operations.

  • To find the smallest or the greatest element in an array.
  • To find the second-best number (runner-up player or the second least/max number)
  • Truck Loading problem.

 

How many external and internal nodes are there in the tournament trees?

Answer: The external nodes or the leaf nodes represent the players in the tournament tree, whereas the internal nodes represent the winner or the loser of the nodes at the underneath level.

Key Takeaways

Congrats on learning something new today!!

In this blog post, we learned a new and fundamental topic: Tournament Trees. Tournament trees are applications of Binary Heaps; hence it requires the knowledge of Binary Trees and heaps.

And make sure to check out this amazing placement preparation course carefully crafted and designed by Coding Ninjas: check your campus preparedness here.

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think