Return to Answer

Philosophy

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

There is no guarantee that "everything to the left is smaller than everything to the right" as for BST.

LRU cache: efficient approach if all insertions are guaranteed to be then min

If every time you insert something it is always the minimum, there's an even more efficient approach to things: you can just keep a hash map to nodes of a linked list: https://stackoverflow.com/questions/2504178/lru-cache-design

BST maintains a global property, heap a local one

This local property, unlike for BSTs, then also implies by itself a global property: an element is smaller than all children.

But there is no guarantee that "everything to the left is smaller than everything to the right" as for BST.

It is also interesting to consider what would happen if we only enforced a local property for BST:

left child is smaller, right child is larger

The problem with this is that because there are two possible directions to consider, smaller or greater, the second level descendant may break the global property, for example consider:

# Fake BST with local property only 5 / \ 3 7 / \ 1 9 

Here, we have the property that "left child is smaller, right child is bigger" for all nodes.

But as we go smaller to 3, the next level can get arbitrarily large to the right, here going up to 9, which is above 5, and so we don't have a global property.

The only global property that would be enforced by that rule alone is if we only go down all the way left we decrease, or all the way right we increase.

In the case of the heap, there is only one possible direction: smaller or bigger at each step, so the global property is also implied.

LRU cache: efficient approach if all insertions are guaranteed to be the max or min

If every time you insert something it is always the maximum or minimum, there's an even more efficient approach to things: you can just keep a hash map to nodes of a linked list: https://stackoverflow.com/questions/2504178/lru-cache-design

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

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

• 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

• 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

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

SVG source adapted from original by Derrick Coetzee.

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

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

There is no guarantee that "everything to the left is smaller than everything to the right" as for BST.

SVG source.

BST vs Heap vs Hashmap

• 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

LRU cache: efficient approach if all insertions are guaranteed to be then min

If every time you insert something it is always the minimum, there's an even more efficient approach to things: you can just keep a hash map to nodes of a linked list: https://stackoverflow.com/questions/2504178/lru-cache-design

The hashmap allows you to quickly remove any element in the middle when needed in O(1) average.

This use case comes up naturally when you are inserting elements with time as their key, and you only want to access the newest or oldest item to do something with that item.

Similar question on CS: What's the difference between a binary search tree and a binary heap?

Similar question: https://stackoverflow.com/questions/6147242/heap-vs-binary-search-tree-bst