Skip to main content

Heaps and Priority Queues

Heapify, Time Complexity of Insert, Delete and Search#

Heap is a tree based data structure, where all the child and parent nodes follow a special condition between them, which will enable you to retrieve the element with either the smallest or the largest value in O(1) time. But what is this special condition? Is there any other special condition? How is it implemented? If any of these questions come to your curioud mind, all you have to do is just read on to find out. Similar to heap, there is another advanced data structure but in order that you are able to appreciate it, it is important you have a clear understanding of heap here and now.

Caution

If you are not able to visualize how the insert, delete operations work in heap, take your time working out a few inputs, follow the algorithm line by line and build a heap, then try performing the operations in detail. Do not proceed further if you are not able to visualise just yet. Following link will help you visualise heap

Q: Can you workout the time complexity of building a heap. Is it O(n) or O(nlogn)? Know Here

Q: Can you answer why to use heap, when the purpose of heap can also be served by maintaining the elements in a sorted manner?

Priority Queue#

To save you the time of implementing heap and prevent you from making unnecessary mistakes, STL in C++ provides Priority Queue which is by default a max heap. Keep on reading and see for yourself what priority queue is all about.

Caution

The following STL utilities for Priority Queue in C++ is a must know : empty(), size(), push(), pop(), top().

Tips

The STL Priority Queue is a max heap by default, to make use of it as a min heap simply store the negative of the original value in the heap, this way the negative of the max element in the heap will be the smallest value. Additionally, you can define priority queue for your own custom data type which is very very handy to know.

Read upto the third answer in this post