Skip to content
BENIBIX Learn

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.

Development🧮 Algorithms & Data Structures

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.

Example
Jack's task runner keeps jobs in a heap by urgency. Whatever is most urgent comes out next, even if it arrived last.
Why it matters
Heaps pick the next job in task lists. Map apps use them to find short routes too.
Full entry
Development🧮 Algorithms & Data Structures

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.

Example
Emma stores 1,000,000 scores in a balanced search tree. Finding one score takes about 20 steps instead of a million.
Why it matters
It gives fast search and keeps items sorted at the same time. Many database indexes use a close cousin of it.
Full entry

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.