Complexity PQ with binary heap

<aside> 📎 * Using a hash table to help optimise these operations does take up linear space and also adds some overhead to be binary heap implementation

</aside>

Complexity analysis of Java Priority Queue

A Heap is a special Tree-based data structure in which the tree is a complete binary tree. Generally, Heaps can be of two types:

1. Max-Heap: In a Max-Heap the key present at the root node must be greatest among the keys present at all of it’s children. The same property must be recursively true for all sub-trees in that Binary Tree.
2. Min-Heap: In a Min-Heap the key present at the root node must be minimum among the keys present at all of it’s children. The same property must be recursively true for all sub-trees in that Binary Tree.

Priority Queue

A priority queue is an Abstract Data Type (ADT) that operates similar to a normal queue except that each element has a certain priority. The priority of the elements in the priority queue determine the order in which elements are removed from the PQ.

Priority queues only supports comparable data, meaning the data inserted into the priority queue must be able to be ordered in some way either from least to greatest or greatest to least. This is so that we are able to assign relative priorities to each element.

When and Where is PQ/Heap used?

• Used in certain implementation of Dijkstra's Shortest Path algorithm.
• Anytime you need the dynamic fetch the 'next best' or 'next worst' element
• Used in Huffman coding (which is often used for lossless data compression)
• Best First Search algorithms such as A* use PQs to continuously grab the next most promising node.
• Used by Minimum Spanning Tree algorithms.

Ways of Implementing a PQ

Priority queues are usually implemented with heaps since this gives them the best possible time complexity.