Core · Module 11 · Lesson 1 of 4
The heap property in an array
A priority queue always hands out its smallest (or largest) item next. A binary heap implements it as a complete tree stored in a plain array, where parents and children are found by arithmetic instead of pointers.
By the end you can
- Explain what a priority queue offers and compare the structures that could implement it
- State the heap property and explain why it is weaker than being sorted
- Store a complete binary tree in an array and find any node's parent and children by index
Builds on Level-order traversal.
01 · A question first
An emergency room always treats the most urgent patient next, while new patients keep arriving. A sorted list makes every arrival O(n), and an unsorted list makes every "who's next?" O(n). A heap makes both O(log n), and it doesn't even need pointers. Where does it keep the tree?
Make a guess before you read on.
02 · The idea
Members only
Unlock the full lesson
This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.
What's inside
- The priority queue
- Choosing a structure
- The heap property
- A tree without pointers
- What a heap is not for
- Heaps in your language
- Pseudocode & Multi-Language Implementations (C++, Java, Python)
- Complexity Derivation, Edge Cases & Common Mistakes
03 · Practice
Something wrong with this lesson? Report a problem