Why is Binary Heap Preferred over BST for Priority Queue? - GeeksforGeeks

Why is Binary Heap Preferred over BST for Priority Queue? - GeeksforGeeks

A Self Balancing Binary Search Tree like AVL Tree, Red-Black Tree, etc can also support above operations with same time complexities.

1. Finding minimum and maximum are not naturally O(1), but can be easily implemented in O(1) by keeping an extra pointer to minimum or maximum and updating the pointer with insertion and deletion if required. With deletion we can update by finding inorder predecessor or successor.
2. Inserting an element is naturally O(Logn)
3. Removing maximum or minimum are also O(Logn)
4. Decrease key can be done in O(Logn) by doing a deletion followed by insertion. See this for details.

So why is Binary Heap Preferred for Priority Queue?

• Since Binary Heap is implemented using arrays, there is always better locality of reference and operations are more cache friendly.
• Although operations are of same time complexity, constants in Binary Search Tree are higher./li>
• We can build a Binary Heap in O(n) time. Self Balancing BSTs require O(nLogn) time to construct.
• Binary Heap doesn't require extra space for pointers.
• Binary Heap is easier to implement.
• There are variations of Binary Heap like Fibonacci Heap that can support insert and decrease-key in Θ(1) time

Read full article from Why is Binary Heap Preferred over BST for Priority Queue? - GeeksforGeeks