Heap vs Binary Search Tree (BST)
People think a heap keeps its items sorted, like a binary search tree. It does not. A search tree keeps every value in order, so you can find any one fast. A heap only keeps the smallest item on top. Pick a heap when you only need the next smallest, and a search tree to look up any value.
Heap (Data Structure)
A tree that keeps the smallest item on top, or the largest.
A heap is a tree that always keeps the smallest item at the top, or the largest in a max-heap. It does not keep everything in order, only enough to find the top item at once. Taking the top item out and adding a new one each take about log n steps. That makes it the usual way to build a priority queue. Python's heapq module gives you one on a plain list.
Binary Search Tree (BST)
A binary tree kept in order. Small values go left; big ones go right.
A binary search tree is a binary tree that keeps its values in order. Everything in a node's left branch is smaller than it, and everything in its right branch is bigger. To find a value, you start at the root and go left or right at each step. If the tree stays balanced, that takes about 20 steps for a million values. If it grows lopsided, it can become as slow as a list.
In one line
- Heap (Data Structure)
- A tree that keeps the smallest item on top, or the largest.
- Binary Search Tree (BST)
- A binary tree kept in order. Small values go left; big ones go right.