Understanding data structures is crucial for efficient software development, and two fundamental ones are the heap and the binary search tree (BST). While both are tree-based structures, they serve different purposes and offer unique performance characteristics. Choosing the right data structure can significantly impact the speed and efficiency of your algorithms. This article will delve into the key differences between heaps and binary search trees, exploring their properties, operations, and use cases, helping you make informed decisions about when to use each. We’ll cover aspects such as the heap property, tree traversal, time complexity for common operations, and provide examples to illustrate their practical applications. Knowing when to use a heap versus a binary search tree is a vital skill for any programmer aiming to optimize their code. Let’s explore these data structures in detail and uncover their strengths and weaknesses.

Heap: Prioritizing Efficiency

A heap is a specialized tree-based data structure that satisfies the heap property. This property dictates the relationship between parent and child nodes. In a min-heap, the value of each node is less than or equal to the value of its children. Conversely, in a max-heap, the value of each node is greater than or equal to the value of its children. This ordering doesn’t imply any specific order between siblings; it only defines the relationship between parents and their direct descendants. Heaps are typically implemented as complete binary trees, meaning all levels are fully filled except possibly the last level, which is filled from left to right. This characteristic makes them particularly efficient for array-based implementations.

The key advantage of a heap lies in its ability to quickly access the minimum (in a min-heap) or maximum (in a max-heap) element. This makes heaps ideal for priority queues, where elements are processed based on their priority. Operations like inserting a new element (insert) and extracting the minimum/maximum element (extract_min or extract_max) have logarithmic time complexity, O(log n), making them very efficient even for large datasets. According to research from MIT, heap data structures are “essential for implementing efficient priority queues and are widely used in algorithms such as Dijkstra’s algorithm and heap sort.” MIT OpenCourseWare - Introduction to Algorithms provides an in-depth analysis of heap implementations and their applications.

Here’s a simple example of how a min-heap can be used: Imagine you’re managing a server farm and need to prioritize tasks based on urgency. Each task can be assigned a priority value, and a min-heap can be used to ensure that the task with the highest urgency (lowest priority value) is always processed first. When a new task arrives, it’s inserted into the heap, and the heap property is maintained through a process called “heapify.” When a task is completed, the root element (minimum value) is extracted, and the heap is re-heapified. This ensures that the server always focuses on the most critical tasks.

Binary Search Tree (BST): Maintaining Order

A binary search tree (BST) is another tree-based data structure, but its defining characteristic is its ordering property: for each node, all nodes in its left subtree have values less than the node’s value, and all nodes in its right subtree have values greater than the node’s value. This property allows for efficient searching, insertion, and deletion of elements. Unlike heaps, BSTs maintain a strict ordering across the entire tree, not just between parent and child nodes. This global ordering makes BSTs suitable for scenarios where ordered data retrieval is essential.

The efficiency of BST operations depends heavily on the tree’s structure. In the best-case scenario, where the tree is balanced, search, insertion, and deletion operations have a time complexity of O(log n). However, in the worst-case scenario, where the tree is skewed (e.g., all nodes are inserted in ascending order), the time complexity degrades to O(n), effectively becoming a linked list. To mitigate this, self-balancing BSTs, such as AVL trees and red-black trees, are often used. These self-balancing trees automatically adjust their structure to maintain a balanced state, ensuring logarithmic time complexity for most operations. GeeksforGeeks provides comprehensive tutorials on various BST implementations, including self-balancing trees.

Consider a scenario where you need to store and retrieve employee records based on their employee ID. A BST would be a suitable data structure for this. Each node in the BST would represent an employee record, and the employee ID would be used as the key. When you need to find a specific employee record, you can traverse the BST based on the employee ID, efficiently locating the desired record. Similarly, inserting a new employee record involves finding the correct position in the BST based on the employee ID, maintaining the overall ordering of the tree.

Key Differences: Heap vs BST

The fundamental distinction between a heap and a BST lies in their ordering properties and intended use cases. While both are tree-based, their structures and functionalities differ significantly. Heaps prioritize quick access to the minimum or maximum element, while BSTs prioritize maintaining a sorted order of all elements. This difference in focus leads to variations in their implementations and performance characteristics. Understanding these differences is crucial for selecting the appropriate data structure for a given task.

Here’s a breakdown of the key differences:

• Ordering: Heaps maintain a partial ordering (parent-child relationship), while BSTs maintain a total ordering (across the entire tree).
• Structure: Heaps are typically implemented as complete binary trees, while BSTs can have varying shapes, including skewed trees.
• Primary Use Case: Heaps are ideal for priority queues and algorithms like heap sort, while BSTs are suitable for scenarios requiring ordered data retrieval and searching.
• Time Complexity: While both can achieve O(log n) for certain operations, BST performance is highly dependent on the tree’s balance.

The key differences are summarized in this featured snippet-optimized paragraph: Heaps are primarily used for priority queues, offering O(log n) time complexity for insertion and extraction of the minimum/maximum element. Their partial ordering focuses on parent-child relationships. In contrast, Binary Search Trees (BSTs) are designed for ordered data retrieval, with O(log n) complexity for search, insertion, and deletion in balanced trees. BSTs maintain a total ordering across all nodes, making them suitable for tasks requiring efficient searching and sorted data access. The choice between a heap and a BST depends on whether the application prioritizes quick access to extreme values or efficient searching and ordered data maintenance.

Let’s consider a practical example. Suppose you need to find the median of a stream of numbers. A heap-based approach, using a min-heap and a max-heap, can efficiently track the lower and upper halves of the data, allowing for quick calculation of the median. On the other hand, if you need to perform range queries (e.g., find all numbers between 10 and 20), a BST would be a more suitable choice, as it allows for efficient searching within a specific range of values.

Implementation and Operations

Implementing heaps and BSTs involves different techniques and considerations. Heaps are often implemented using arrays, leveraging the complete binary tree structure for efficient indexing. The parent and child nodes can be easily calculated using array indices, simplifying the implementation of operations like insert and extract_min. BSTs, on the other hand, are typically implemented using linked nodes, where each node contains pointers to its left and right children. This allows for more flexibility in terms of tree structure, but also requires careful management of pointers during insertion and deletion.

The operations performed on heaps and BSTs also differ in their implementation. Heap operations like insert involve adding a new element to the end of the array and then “heapifying” the tree to restore the heap property. The “heapify” process involves comparing the new element with its parent and swapping them if necessary, repeating this process until the heap property is satisfied. BST operations like insert involve traversing the tree to find the appropriate position for the new node based on its value. Once the position is found, the new node is inserted as a child of the appropriate parent node. Deletion in a BST is more complex, requiring consideration of different cases, such as deleting a node with no children, one child, or two children. VisuAlgo offers interactive visualizations of various data structures and algorithms, including heaps and BSTs, which can be helpful for understanding their implementation.

Here’s a step-by-step guide to inserting an element into a min-heap:

1. Add the new element to the end of the heap (array).
2. Compare the new element with its parent.
3. If the new element is smaller than its parent, swap them.
4. Repeat steps 2 and 3 until the new element is in its correct position or it becomes the root.

Consider the following example scenario: You are building a system to manage customer support tickets. You need to efficiently prioritize tickets based on their urgency. You could use a heap to ensure the most urgent tickets are always handled first. Alternatively, if you need to quickly search for tickets based on their ID and also retrieve them in sorted order, a BST might be a better choice.

When should I use a heap instead of a BST?

Use a heap when you need quick access to the minimum or maximum element and don't require a fully sorted data structure. Priority queues are a common use case.

What are the advantages of a self-balancing BST?

Self-balancing BSTs (e.g., AVL trees, red-black trees) guarantee logarithmic time complexity for search, insertion, and deletion operations, preventing performance degradation in skewed trees.

Can a heap be used for sorting?

Yes, a heap can be used for sorting using the heap sort algorithm, which has a time complexity of O(n log n).

Is a BST always more efficient than a heap for searching?

Not always. While BSTs are generally efficient for searching, heaps can be faster for finding the minimum or maximum element. The best choice depends on the specific search requirements.

Question & Answer :
What is the difference between a heap and BST?

When to use a heap and when to use a BST?

If you want to get the elements in a sorted fashion, is BST better over heap?

Summary

Type BST (*) Heap Insert average log(n) 1 Insert worst log(n) log(n) or n (***) Find any worst log(n) n Find max worst 1 (**) 1 Create worst n log(n) n Delete worst log(n) log(n) 

All average times on this table are the same as their worst times except for Insert.

• *: everywhere in this answer, BST == Balanced BST, since unbalanced sucks asymptotically
• **: using a trivial modification explained in this answer
• ***: log(n) for pointer tree heap, n for dynamic array heap

Advantages of binary heap over a BST

• average time insertion into a binary heap is O(1), for BST is O(log(n)). This is the killer feature of heaps.

  There are also other heaps which reach O(1) amortized (stronger) like the Fibonacci Heap, and even worst case, like the Brodal queue, although they may not be practical because of non-asymptotic performance: Are Fibonacci heaps or Brodal queues used in practice anywhere?

• binary heaps can be efficiently implemented on top of either dynamic arrays or pointer-based trees, BST only pointer-based trees. So for the heap we can choose the more space efficient array implementation, if we can afford occasional resize latencies.

• binary heap creation is O(n) worst case, O(n log(n)) for BST.

Advantage of BST over binary heap

• search for arbitrary elements is O(log(n)). This is the killer feature of BSTs.

  For heap, it is O(n) in general, except for the largest element which is O(1).

“False” advantage of heap over BST

• heap is O(1) to find max, BST O(log(n)).

  This is a common misconception, because it is trivial to modify a BST to keep track of the largest element, and update it whenever that element could be changed: on insertion of a larger one swap, on removal find the second largest. Can we use binary search tree to simulate heap operation? (mentioned by Yeo).

  Actually, this is a limitation of heaps compared to BSTs: the only efficient search is that for the largest element.

Average binary heap insert is O(1)

Sources:

• Paper: http://i.stanford.edu/pub/cstr/reports/cs/tr/74/460/CS-TR-74-460.pdf
• WSU slides: - WSU slides: https://web.archive.org/web/20161109132222/http://www.eecs.wsu.edu/~holder/courses/CptS223/spr09/slides/heaps.pdf

Intuitive argument:

• bottom tree levels have exponentially more elements than top levels, so new elements are almost certain to go at the bottom
• heap insertion starts from the bottom, BST must start from the top

In a binary heap, increasing the value at a given index is also O(1) for the same reason. But if you want to do that, it is likely that you will want to keep an extra index up-to-date on heap operations How to implement O(logn) decrease-key operation for min-heap based Priority Queue? e.g. for Dijkstra. Possible at no extra time cost.

GCC C++ standard library insert benchmark on real hardware

I benchmarked the C++ std::set (Red-black tree BST) and std::priority_queue (dynamic array heap) insert to see if I was right about the insert times, and this is what I got:

• benchmark code
• plot script
• plot data
• tested on Ubuntu 19.04, GCC 8.3.0 in a Lenovo ThinkPad P51 laptop with CPU: Intel Core i7-7820HQ CPU (4 cores / 8 threads, 2.90 GHz base, 8 MB cache), RAM: 2x Samsung M471A2K43BB1-CRC (2x 16GiB, 2400 Mbps), SSD: Samsung MZVLB512HAJQ-000L7 (512GB, 3,000 MB/s)

So clearly:

• heap insert time is basically constant.

  We can clearly see dynamic array resize points. Since we are averaging every 10k inserts to be able to see anything at all above system noise, those peaks are in fact about 10k times larger than shown!

  The zoomed graph excludes essentially only the array resize points, and shows that almost all inserts fall under 25 nanoseconds.

• BST is logarithmic. All inserts are much slower than the average heap insert.

• BST vs hashmap detailed analysis at: What data structure is inside std::map in C++?

GCC C++ standard library insert benchmark on gem5

gem5 is a full system simulator, and therefore provides an infinitely accurate clock with with m5 dumpstats. So I tried to use it to estimate timings for individual inserts.

Interpretation:

• heap is still constant, but now we see in more detail that there are a few lines, and each higher line is more sparse.

  This must correspond to memory access latencies are done for higher and higher inserts.

• TODO I can’t really interpret the BST fully one as it does not look so logarithmic and somewhat more constant.

  With this greater detail however we can see can also see a few distinct lines, but I’m not sure what they represent: I would expect the bottom line to be thinner, since we insert top bottom?

Benchmarked with this Buildroot setup on an aarch64 HPI CPU.

BST cannot be efficiently implemented on an array

Heap operations only need to bubble up or down a single tree branch, so O(log(n)) worst case swaps, O(1) average.

Keeping a BST balanced requires tree rotations, which can change the top element for another one, and would require moving the entire array around (O(n)).

Heaps can be efficiently implemented on an array

Parent and children indexes can be computed from the current index as shown here.

There are no balancing operations like BST.

Delete min is the most worrying operation as it has to be top down. But it can always be done by “percolating down” a single branch of the heap as explained here. This leads to an O(log(n)) worst case, since the heap is always well balanced.

If you are inserting a single node for every one you remove, then you lose the advantage of the asymptotic O(1) average insert that heaps provide as the delete would dominate, and you might as well use a BST. Dijkstra however updates nodes several times for each removal, so we are fine.

Dynamic array heaps vs pointer tree heaps

Heaps can be efficiently implemented on top of pointer heaps: Is it possible to make efficient pointer-based binary heap implementations?

The dynamic array implementation is more space efficient. Suppose that each heap element contains just a pointer to a struct:

• the tree implementation must store three pointers for each element: parent, left child and right child. So the memory usage is always 4n (3 tree pointers + 1 struct pointer).

  Tree BSTs would also need further balancing information, e.g. black-red-ness.

• the dynamic array implementation can be of size 2n just after a doubling. So on average it is going to be 1.5n.

On the other hand, the tree heap has better worst case insert, because copying the backing dynamic array to double its size takes O(n) worst case, while the tree heap just does new small allocations for each node.

Still, the backing array doubling is O(1) amortized, so it comes down to a maximum latency consideration. Mentioned here.

Philosophy

• BSTs maintain a global property between a parent and all descendants (left smaller, right bigger).

  The top node of a BST is the middle element, which requires global knowledge to maintain (knowing how many smaller and larger elements are there).

  This global property is more expensive to maintain (log n insert), but gives more powerful searches (log n search).

• Heaps maintain a local property between parent and direct children (parent > children).

  The top node of a heap is the big element, which only requires local knowledge to maintain (knowing your parent).

Comparing BST vs Heap vs Hashmap:

• BST: can either be either a reasonable:

  • unordered set (a structure that determines if an element was previously inserted or not). But hashmap tends to be better due to O(1) amortized insert.
  • sorting machine. But heap is generally better at that, which is why heapsort is much more widely known than tree sort

• heap: is just a sorting machine. Cannot be an efficient unordered set, because you can only check for the smallest/largest element fast.

• hash map: can only be an unordered set, not an efficient sorting machine, because the hashing mixes up any ordering.

Doubly-linked list

A doubly linked list can be seen as subset of the heap where first item has greatest priority, so let’s compare them here as well:

• insertion:
  • position:
    • doubly linked list: the inserted item must be either the first or last, as we only have pointers to those elements (unless we have a pointer to the position of interest e.g. during iteration)
    • binary heap: the inserted item can end up in any position. Less restrictive than linked list.
  • time:
    • doubly linked list: O(1) worst case since we have pointers to the items, and the update is really simple
    • binary heap: O(1) average, thus worse than linked list. Tradeoff for having more general insertion position.
• search: O(n) for both

An use case for this is when the key of the heap is the current timestamp: in that case, new entries will always go to the beginning of the list. So we can even forget the exact timestamp altogether, and just keep the position in the list as the priority.

This can be used to implement an LRU cache. Just like for heap applications like Dijkstra, you will want to keep an additional hashmap from the key to the corresponding node of the list, to find which node to update quickly.

Comparison of different Balanced BST

Although the asymptotic insert and find times for all data structures that are commonly classified as “Balanced BSTs” that I’ve seen so far is the same, different BBSTs do have different trade-offs. I haven’t fully studied this yet, but it would be good to summarize these trade-offs here:

• Red-black tree. Appears to be the most commonly used BBST as of 2019, e.g. it is the one used by the GCC 8.3.0 C++ implementation
• AVL tree. Appears to be a bit more balanced than BST, so it could be better for find latency, at the cost of slightly more expensive finds. Wiki summarizes: “AVL trees are often compared with red–black trees because both support the same set of operations and take [the same] time for the basic operations. For lookup-intensive applications, AVL trees are faster than red–black trees because they are more strictly balanced. Similar to red–black trees, AVL trees are height-balanced. Both are, in general, neither weight-balanced nor mu-balanced for any mu < 1/2; that is, sibling nodes can have hugely differing numbers of descendants.”
• WAVL. The original paper mentions advantages of that version in terms of bounds on rebalancing and rotation operations.

See also

Similar question on CS: https://cs.stackexchange.com/questions/27860/whats-the-difference-between-a-binary-search-tree-and-a-binary-heap