floor and ceiling
Rounding functions: floor rounds a number down to the nearest whole number and ceiling rounds it up.
In more detail
A heap node's parent index is floor((i - 1) / 2), written (i - 1) // 2 in Python. A B-tree's height bound uses the ceiling of a logarithm, since a partial level still counts as a level.
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.
- logarithm — The number of times you must divide a number by a base, usually two in computing, to get down to one.
Taught in
- Recognising The Common Growth Rates — Algorithms & Data Structures for Working Engineers
- Big O, Big Omega And Big Theta — Algorithms & Data Structures for Working Engineers
- AVL Trees: Rotations That Keep The Guarantee — Algorithms & Data Structures for Working Engineers
- B-Trees: The Structure Behind Every Database Index — Algorithms & Data Structures for Working Engineers
- Heaps And Priority Queues — Algorithms & Data Structures for Working Engineers