Why is Binary Heap Preferred over BST for Priority Queue

A priority queue is a linear and ordered collection of elements in which each element has an attribute named priority and the priority attribute decides the order in which elements are deleted and processed. Each process performed on the element must follow the following rule:

• Higher priority element is processed before any element of lower priority elements, and
• The clash between two elements with the same priority is resolved by the order in which they are added to the priority queue.

A priority queue is built to process the following operations in less amount of time (efficiently):

• Get the highest priority element (Smallest or largest)
• Deletion of the highest priority element
• Insertion – Insertion of an element with some priority at its right place in the queue
• Decrease Key – Decrease the value of a specific element or key

A binary heap supports these operations with the following time complexities:

• Highest Priority element in O(1),
• Deletion of the Highest Priority element in O(Log N),
• Insertion in O(Log N), and
• Decrease Key in O(Log N).

A binary search tree (BST) supports these operations with the following time complexities:

• Highest Priority element in O(N),
• Deletion of the Highest Priority element in O(N),
• Insertion in O(N), and
• Decrease Key in O(N).

An AVL Tree (Self-balancing binary tree) supports the above-required operations with the following time complexities:

• Highest Priority element in O(Log N) but can be found in O(1) by keeping an additional pointer to the highest priority element. Also, we need to update the pointer after each insertion and deletion,
• Deletion of the Highest Priority element in O(Log N),
• Insertion in O(Log N), and
• Decrease Key in O(Log N)

So, the following are the reasons why a binary heap is preferred over BST for the priority queue:

1. A heap is implemented using an array. So, all the operations performed are more friendly for the users, and we get a better locality of reference.
2. A heap is constructed in O(Log N) time, whereas the self-balancing tree requires O(N Log N) time.
3. Building a binary heap is less complex than building a BST or AVL tree.
4. The BST or AVL tree requires extra space for pointers, whereas a binary heap is free from pointers.
5. The Fibonacci tree one of the variants of the binary heap can support the insertion and the decrease-key operation in constant time i.e., Q(1).

Although, for some operations, the AVL tree performs better than the binary heap. So, the heap are not always preferred over BSTs, and the following are the reasons:

1. Searching in an AVL tree requires (Log N) times, but a binary heap requires O(N),
2. The time complexities of printing the sorted sequence of elements using an AVL tree and a binary heap are O(Log N) and O(N Log N), respectively,
3. It costs O(Log N) time is finding the kth-largest or smallest element, and
4. The nearest largest (ceil) and smallest (floor) can be found in O(Log N) time.