Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

share|improve this question
1  
The expression "runtime complexity of [data structure]" does not make any sense. –  Raphael Apr 9 at 21:34

6 Answers 6

up vote 12 down vote accepted

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

share|improve this answer
    
I think BST is better in findMin & findMax stackoverflow.com/a/27074221/764592 –  Yeo Nov 22 '14 at 5:50
    
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 –  Ciro Santilli 六四事件 法轮功 纳米比亚胡海峰 Jun 20 at 5:01

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

share|improve this answer

Both binary search trees and binary heaps are both in the set of trees and 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.

share|improve this answer
3  
Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. –  FrankW Jun 20 '14 at 7:17
    
Insertion into binary heaps is $O(\log n)$, not $O(1)$. What is $O(1)$ is extract_min/extract_max. –  FrankW Jun 20 '14 at 7:18

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.

share|improve this answer

Advantages of binary heap over a balanced 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.

  • binary heaps can be efficiently implemented on top of arrays, BST cannot.

    So we don't have to store 3 pointers per node (left, right, parent) plus balancing data (e.g. RB-ness), saving memory by a constant factor.

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

Advantage of BST over binary heap:

  • search for arbitrary elements O(log(n)), O(n) for heap, in which the only fast search is for the largest element O(1). This is the killer feature of BSTs.

"False" advantage of heap over BST:

More detailed discussion of the hardest points mentioned above.

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

BST cannot be efficiently implemented on an array

Heap operations only need to bubble up or down a single tree branch.

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

Philosophy

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

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

  • 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).

See also

share|improve this answer

A Heap a number on top MUST be bigger than it's children.

A BST the numbers to the left MUST be smaller than its parent. The numbers on the right must be bigger than its parent.

A BST is MUCH better for a search where you must find a specific number in general IMO. Since it slowly pinpoints where the number is if it exists.

A Heap on the other hand you will have to check both each side because the number/value you are looking for may exist else where. WHILE on a BST if it isn't in a particular place you know it doesn't exist in this tree.

share|improve this answer
1  
What does this add to the previous answers? –  dfeuer Mar 18 at 1:00
    
Thanks for taking the time to contribute an answer but that time would have been better spent writing something that added to the existing answers, rather than duplicating them. It's also not very useful to inject opinion ("IMO") where concrete performance analysis could have been used (general find in a BST is $O(\log n)$ vs $O(n)$ in a heap) or to describe searching in a BST ($O(\log n)$) as "slow". –  David Richerby Mar 18 at 7:43
    
This was answered the day before. It's over already. –  bfs Mar 18 at 23:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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