Course contentsShow
← Computer Science
Lesson 584 of 2,87214. Heaps and Priority QueuesFree lesson

Comparing Heaps to BSTs

Contrast heap ordering (parent-child only) with BST ordering (left-parent-right), understanding their different use cases.

Comparing Heaps to BSTs

You'll learn: How heaps and binary search trees organize data differently and why that makes them suited for different tasks.

The Fundamental Difference

Both heaps and BSTs are binary tree structures, but they enforce completely different ordering rules:

BSTs maintain a strict left-parent-right ordering across the entire tree. For any node, all values in the left subtree must be smaller, and all values in the right subtree must be larger. This creates a global ordering that allows you to traverse the tree in sorted order.

Heaps only care about parent-child relationships. In a max-heap, a parent must be ≥ its children—but siblings have no ordering requirement. The left child could be larger or smaller than the right child. The heap property is purely vertical (along parent-child edges), not horizontal.

What This Means in Practice

Imagine you have values: 50, 30, 40, 10, 20

In a BST: You could find any value efficiently by comparing at each node and going left or right. The tree maintains a searchable structure.

In a heap: The only guarantee is that 50 is at the root (max-heap), and each parent is larger than its children. You cannot efficiently search for 30—you might have to check many paths because there's no rule about which subtree contains larger values.

Use Case Alignment

  • BSTs excel at: Search, finding min/max, range queries, sorted traversal
  • Heaps excel at: Quickly accessing the maximum (or minimum) element, priority-based processing

Heaps trade away search capability for better insertion/deletion of the extreme element and the complete tree shape that enables efficient array representation.

Key Takeaway: Heaps enforce only parent > child ordering (vertical), while BSTs enforce left < parent < right ordering (global); this makes heaps perfect for priority queues but poor for general searching.