A lesson from the Data Structures module of the 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 curriculum of a structure that is exactly as ordered as it needs to be and no more, and that 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) that follows the heap property: in a min-heap every parent is smaller than both its children, and in a max-heap every parent is larger. That is the whole rule, and notice what it does NOT say. Nothing about siblings, nothing about cousins, nothing about the order of two nodes on different branches. A heap is not sorted, and you cannot search it in less than O(n). What you get is one guarantee: the item at the root is the minimum (or maximum) of everything in it. The people who get surprised by heaps are the people who expected more than that.
The rest of this lesson continues with 5 further sections. See the full curriculum.
Browse all 576 practice puzzles