93
$\begingroup$

These two seem very similar and have almost an identical structure. What's the difference? What are the time complexities for different operations of each?

$\endgroup$
64
$\begingroup$

Heap just guarantees that elements on higher levels are greater (for max-heap) or smaller (for min-heap) than elements on lower levels, whereas BST guarantees order (from "left" to "right"). If you want sorted elements, go with BST.by Dante is not a geek

Heap is better at findMin/findMax (O(1)), while BST is good at all finds (O(logN)). Insert is O(logN) for both structures. If you only care about findMin/findMax (e.g. priority-related), go with heap. If you want everything sorted, go with BST.

by xysun

$\endgroup$
  • $\begingroup$ I think BST is better in findMin & findMax stackoverflow.com/a/27074221/764592 $\endgroup$ – Yeo Nov 22 '14 at 5:50
  • 10
    $\begingroup$ I think this is just a common misconception. A binary tree can be easily modified to find min and max as pointed by Yeo. This is actually a restriction of the heap: the only efficient find is min or max. The true advantage of the heap is O(1) average insert as I explain: stackoverflow.com/a/29548834/895245 $\endgroup$ – Ciro Santilli 新疆改造中心法轮功六四事件 Jun 20 '15 at 5:01
  • $\begingroup$ According to this video, you can have larger values on a lower level, as long as the larger is not descendant of the lower one. $\endgroup$ – whoan Jun 21 '17 at 0:08
  • $\begingroup$ Heap is sorted root to leaf and BST is sorted left to right. $\endgroup$ – Deep Joshi Aug 21 '18 at 9:58
34
$\begingroup$

Both binary search trees and binary heaps are tree-based data structures.

Heaps require the nodes to have a priority over their children. In a max heap, each node's children must be less than itself. This is the opposite for a min heap:

Binary Max Heap

Binary search trees (BST) follow a specific ordering (pre-order, in-order, post-order) among sibling nodes. The tree must be sorted, unlike heaps:

Binary Search Tree

BST have average of $O(\log n)$ for insertion, deletion, and search.
Binary Heaps have average $O(1)$ for findMin/findMax and $O(\log n)$ for insertion and deletion.

$\endgroup$
  • 1
    $\begingroup$ @FrankW Extraction is $O(\log n)$, no? $\endgroup$ – flow2k Aug 6 '18 at 22:57
33
$\begingroup$

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

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

Average binary heap insert is O(1)

Sources:

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 https://stackoverflow.com/questions/17009056/how-to-implement-ologn-decrease-key-operation-for-min-heap-based-priority-queu 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:

enter image description here

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

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.

enter image description here

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: https://stackoverflow.com/questions/19720438/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 note 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.
      • 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: What's the difference between a binary search tree and a binary heap?

$\endgroup$
  • 1
    $\begingroup$ Great answer. Common application of heap are median, k min, top k elements. For these most common operation remove min then insert(usually we have small heap with few pure insert operations). So seems like in practice, for these algorithms it does not outperform BST. $\endgroup$ – yura Jun 19 '16 at 19:25
  • 1
    $\begingroup$ Exceptional answer!!! By using deque as underlying heap structure, you can dramatically reduce resize times, although it still be O(n) worst case since it needs to realloc (smaller) array of pointers to chunks. $\endgroup$ – Bulat Aug 22 '18 at 9:54
13
$\begingroup$

With data structure one has to distinguish levels of concern.

  1. The abstract data structures (objects stored, their operations) in this question are different. One implements a priority queue, the other a set. A priority queue is not interested in finding an arbitrary element, only the one with largest priority.

  2. The concrete implementation of the structures. Here on first sight both are (binary) trees, with different structural properties though. Both the relative ordering of the keys and the possible global structures differ. (Somewhat imprecise, in a BST keys are ordered left-to-right, in a heap they are ordered top-down.) As IPlant correctly remarks an heap should also be "complete".

  3. There is a final difference in the low level implementation. A (unbalanced) binary search-tree has a standard implementation using pointers. A binary heap to the contrary has an efficient implementation using an array (precisely because of the restricted structure).

$\endgroup$
1
$\begingroup$

On top of the previous answers, the heap must have the heap structure property; the tree must be full, and the bottom most layer, which cannot always be full, must be filled leftmost to rightmost with no gaps.

$\endgroup$

protected by Community Aug 25 '18 at 15:09

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.