As I understand, a max-heap is binary tree where the parent is either greater than, or smaller than its right/left child respectively.
Does this mean that a leaf of a binary tree is by definition a max-heap?
1 Answers
Yes, a leaf of a tree is itself a heap. In other words, a tree with just one node is a heap -- both a min-heap and a max-heap, since there is no second value to compare with.
This is also the reason why the typical heap building process (given an array), starts with an index in the middle of the array. This references the last node that still is a parent. Quoting Wikipedia:
The array elements indexed by floor(/2) + 1, floor(/2) + 2, ..., are all leaves for the tree (assuming that indices start at 1) — thus each is a one-element heap, and does not need to be down-heapified.
Related