These two seem very similar and have almost an identical structure. What's the difference? What are the runtime complexities of each?
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 search trees (BST) follow a specific ordering (pre-order, in-order, post-order) among sibling nodes. The tree must be sorted, unlike heaps:
BST have average of $O(\log n)$ for insertion, deletion, and search.
With data structure one has to distinguish levels of concern.
Advantages of binary heap over a balanced BST
Advantage of BST over binary heap
"False" advantage of heap over BST
Average binary heap insert is O(1)
In a binary heap, increasing the value at a given index is also
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.
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:
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.
Similar question on SO: http://stackoverflow.com/questions/6147242/heap-vs-binary-search-tree-bst
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.