Series 4: Heap Examples

Priority Queue

A Priority Queue is an extension of the data structure Queue and can only contain comparable elements. This means that the elements are either arranged in ascending or descending order. Every element in a Priority Queue has a priority associated with it.

An element with a higher priority is Dequeued first as compared to an element with a lower priority. If there are two elements which have the same priority then they are dequeued based on their position within the Priority Queue. One of the most common example of a Priority Queue usage is for CPU Scheduling, i.e, switching between various tasks in an Operating System(OS). Priority Queue's are used in lossless data compression using Huffman coding method. It is also used in the implementation of some of the algorithms like Dijkstra's algorithm , Prim's Minimum Spanning Tree algorithm etc. You can find the implementation details of these algorithms in our upcoming blogs.

The easiest implementation of a Priority Queue is by using a Binary Heap. In this implementation the elements in the Heap are rearranged not only based on whether they are higher or lower than the parent node but also if the priority of the current node is higher than the priority of the parent node. In this way the elements with highest priorities will always be moved to the front of the array/queue and the elements with lowest priorities will be moved to the back of the array/queue. A Priority Queue can be implemented using either a Max Heap or a Min Heap.

Heap Sort

Sorting an array of elements is one of the most compute intensive tasks one can perform. Some of the best sorting algorithms can only offer time complexities between quadratic to logarithmic time complexities. We can use a Heap to sort the elements in an array. This can be done using a Min Binary Heap or a Max Binary Heap.

The idea is to build a Max Heap containing the elements of an array and then sort the elements in place.

Confused?

Let us break this down in to 3 steps:

1. Build a Max Binary Heap with the elements from the array given as input.
2. Now that we have the Heap, the root element will be the element with the maximum value. Let us go ahead and swap this with the last element/child in the Heap(1-D Array). Let us now rebuild the Heap by excluding the last element as it is already in the final position.
3. Repeat Step 2 until all the elements are in their correct positions. The final sorted array is the result.

You can find the full implementation of a Heap Sort at the following location:

With this I hope you have a fair understanding of Heap Data Structure and it's practical uses.Now we need to follow Gopher on his next adventure to learn about our next data structure.