A Comparison of Performances between TreeMap and PriorityQueue in One Use Case

Use Case

Peter is building a mobile app which downloads a lot images from the web and displays them. The server provides different resolutions for each image, which comes in the following format:

{480, "url_for_w480"}
{768, "url_for_w768"}
{1280, "url_for_w1280"}
{1920, "url_for_w1920"}

The integer before the comma represents the width of the image (number of pixels), and the string after the comma is the URL to download this image.

Peter needs to find the image whose width is larger than the screen width of the mobile device. In case the device screen width is larger than all of the images’, the image of the highest resolution should be downloaded.

Let’s say he can get the device’s screen width by calling a method

final int screenWidth = Device.getScreenWidth();

At the same time, he doesn’t want to download an image whose resolution is higher than necessary. For example, when the screenWidth is 500 and Peter gets this response from the server:

{768, "url_for_w768"}
{1280, "url_for_w1280"}

The image of width 768 should be used instead of the one of 1280 to save network bandwidth and device battery.

Problem

Because of a mistake on the server, the image data entries became randomly ordered. So it could come in the following form:

{768, "url_for_w768"}
{1920, "url_for_w1920"}
{480, "url_for_w480"}
{1280, "url_for_w1280"}

Peter needs to find the most efficient way to find the most suitable image URL to be used.

Solutions

There are many solutions to this problem. For example, we can sort the image data entries by width and then use binary search to find the best entry.

Here we want to have a look at the performances of two possible solutions:

1. TreeMap
2. PriorityQueue

TreeMap

1. put all entries into a TreeMap and they will be sorted;
2. iterate from the beginning to the last entry, whenever an image whose width is larger than the screen width is found, return its URL;
3. If none of the images’ widths is larger than the screen width, use the last entry’s URL, which has the highest resolution.

The Comparator:

Test the method against 50,000 test samples and performances is shown as follows:

PriorityQueue

1. enqueue all entries into a PriorityQueue;
2. poll from the front of the PriorityQueue until there is only one entry left in the queue; whenever an image whose width is larger than the screen width is found, return its URL;
3. If none of the previous images’ widths is larger than the screen width, use the last entry’s URL, which has the highest resolution.

The Comparator:

Test the method against 50,000 test samples and performances is shown as follows:

Conclusion

TreeMap is slightly faster than PriorityQueue (18s VS 21s);

At its peak, TreeMap uses more than 3 times of amount of memory than PriorityQueue does (183.298712 megabyte VS 54.167816 megabyte)

The underlying data structure of a TreeMap is Red-black Tree, while the insertion time is (logN), every time a element is being inserted, it creates an Object to wrap the element, which is called Entry. That could explain the extra memory usages of TreeMap.

And the underlying data structure of a PriorityQueue is a Heap, whose elements are stored in an array, which does NOT need a wrapper Object for each element, and the insertion and polling time is also (logN).