1.
Introduction
2.
What is a priority queue?
3.
Operations required in a priority queue
4.
Working of Binary Heap in comparison to that of Binary Search Tree (BST)
5.
Structure of binary heaps
6.
Why are Binary heap and BST used for priority queue?
7.
Advantages of Binary heap over BST
8.
FAQs
9.
Key takeaways
Last Updated: Mar 27, 2024

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

Reet Maggo
1 upvote

## Introduction

In order to understand why binary heap is better than binary search tree for priority queues, it is essential first to understand what a priority queue is, the operations required in a priority queue, and then we will compare the two techniques in terms of their efficiency.

In this blog, we will also discuss the working of the binary heap and compare it to the working of binary search tree (BST), along with its advantages over BST.

## What is a priority queue?

A priority queue is an abstract data type but is quite similar to ordinary queues or stack Data Structure elements with each element being assigned a “priority” in the queue and making the top priority elements available first.

## 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:

## 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.

## 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.