What's the difference between a binary search tree and a binary heap?

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.


 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.

• 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 by practical because of non-asymptotic performance: http://stackoverflow.com/questions/30782636/are-fibonacci-heaps-or-brodal-queues-used-in-practice-anywhere
• 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.

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

• heap is O(1) to find max, BST O(log(n)).
  This is a common misconception, because it is trivial to modify a balanced 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.http://stackoverflow.com/questions/7878622/can-we-use-binary-search-tree-to-simulate-heap-operation (mentioned by Yeo).
  Actually, this is a limitation of heaps: the only efficient search is that for the largest element.