heap property
The rule that every parent in a heap is ordered before its children: no larger than them in a min-heap.
In more detail
It is weaker than the BST rule: siblings can be in any order, so a heap is not sorted and cannot be searched quickly. It only guarantees that the root is the extreme value, which is all a priority queue needs.
Related terms
- binary heap — A complete binary tree stored in an array in which every parent is ordered before its children, so the smallest (or largest) item is always at the root.
- min-heap — A heap in which every parent is less than or equal to its children, so the minimum is at the root; a max-heap reverses the order.
- BST property — The rule that keeps a binary search tree searchable: left subtree keys are smaller than the node, right subtree keys are larger.
Taught in
- Heaps And Priority Queues — Algorithms & Data Structures for Working Engineers