A lesson from the data structures and algorithms bootcamp. About a 12 minute read.
A heap keeps the smallest or largest item ready at the top for O(1) peeking, and it does it while being a tree stored in a flat array with no pointers anywhere. It is the cleanest example in this whole curriculum of a structure that is exactly as ordered as it needs to be and no more, which is where its speed comes from.
A binary heap is a COMPLETE binary tree (every level full except possibly the last, which fills left to right) satisfying the heap property: every parent is smaller than both its children in a min-heap, or larger in a max-heap. That is the whole invariant, and notice what it does NOT say. It says nothing about siblings, nothing about cousins, and nothing about the relative order of two nodes on different branches. A heap is not sorted and cannot be searched in less than O(n). What you get is one guarantee: the item at the root is the minimum (or maximum) of everything in the structure. People who expect more than that from a heap are the people who get surprised by it.
The rest of this lesson continues with 5 further sections. See the full curriculum.
Browse all 536 practice puzzles