Why Binary Heap is Better than Binary Search Tree (BST) for Priority Queues

Operations required in a priority queue

Operations required in an ideal priority queue include

• Obtaining the top priority element
• Deleting top priority elements
• Insertion of new elements
• Decrease key.

Working of Binary Heap in comparison to that of Binary Search Tree (BST)

While a heap is represented as an array of numbers that allows duplication within itself, the BST is an ordered data structure that does not allow duplicates.

Duplication in binary heaps is allowed because the nodes have values lesser than or equal to the root. Heaps that are complete Binary Trees have the minimum height possible and can be created in linear time while the BST takes O (N * log ( N ) ) to build.

Structure of binary heaps

In binary heaps, instead of each node pointing towards the next one like the linked lists, each node can have none, one or two child nodes. In every node, the stored key is either less than or equal to(≤), or greater than or equal to (≥) the children nodes according to the type of heap. Binary heaps use comparison-based sorting, and they further may be min-heap with child nodes being greater than or equal to the parent node, or max-heap with child nodes being lesser than or equal to the parent node.

Why are Binary heap and BST used for priority queue?

Consider each of the tokens representing a task with its assigned priority. The tasks could be arranged in arrays with the top priority element being first. This could definitely help quickly picking up the top priority from the given options, but fixed arrays would not allow the addition of a new task (2). 

An alternative could be a linked list with nodes. New data(7) could be added in this case but the operation would be inefficient as the list would be searched at every node to find the right place to insert a new element (7).

In such situations, Binary heaps could be of great use. Binary heaps are too made up of nodes of data but the nodes are structured in binary trees. They provide a very efficient way of storing data, allowing insertion and deletion and quick access to top priority elements. 

Binary Search Tree or BST also allows operations such as insertion and deletion, search, floor, ceil, etc. Moreover, self-balancing BST is also used to maintain streams of data in an organised manner.

However, why Binary Heap is better than Binary Search Tree for priority queue will be understood by the given points:

Must Read Difference between ArrayList and LinkedList

Advantages of Binary heap over BST

• The time taken to build a Binary Heap is O( N ), which is less than O (N log N) for BST.
  You can visit this link for time complexity analysis.
• Binary heaps have an easier implementation in comparison to BST and use less memory. Since heaps are implemented as arrays, there is no overhead for storing pointers.
• Fibonacci heaps are binary heaps that support increase and decrease keys efficiently.
• No extra space is required for pointers in Binary Heap.
• Binary heap provides a better locality of reference because its implementation uses arrays.
   

You can also read about insertion into bst.

FAQs

1. What are some advantages of BST over Binary Heap?
   The elements of Binary Heap can be traversed in O( N * log ( N ) ) time, which is costlier than the O ( N ) for BST.
   The time complexity for Floor and ceil in BST is O ( log N)
    
2. Are binary trees the same as binary search trees?
   An ordered binary tree is called a Binary Search Tree. It is a non-linear data structure with the maximum number of nodes allowed for a parent node being two-meaning the number of children can be zero, one or two. It is ordered such that the nodes in the tree are organised.
    
3. What are the min and max-heap properties in a binary heap?
   For min-heap, the child node has a value greater than or equal to the parent node and the minimum value element is at the root; for max-heap, child node has value less than or equal to its parent node, and the maximum value element is at the root.
    
4. What are some advantages of BST?
   Time complexity of insert and delete functions is O ( log N ), N being the number of nodes in BST.
   Ordering of keys can be stored in the tree to traverse the order of keys.
   Range queries can be done to find keys between two given variables.
   Order statistics such as the Nth smallest or largest element can be implemented using BST.
    
5. Is binary search tree a heap?
   Binary Search Tree is not a heap. While the BST is an ordered data structure, the heap is not, and is generally represented as an array of numbers.

Key takeaways

In this article, we learned about the structure of Binary Heap, its working in comparison to BST and why it is a better choice for priority queue.

Recommended Reading -

• Application of Priority Queue
• Advantages of Circular Queue

Recommended problems -

• Binary Array Sorting
• Vertical Order Traversal of a Binary Tree
• Leaf Nodes in Binary Tree

Understanding the structure of Binary Heap along with graphical representation helps remember and retain it for longer. Practicing to understand and implement the concepts will definitely make them more concrete. You may visit Coding Ninjas Studio to find thousands of practice questions, and interview experiences of scholars.