Heapify transforms an existing array into a valid heap. Unlike sorting or inserting elements one at a time, it builds the heap directly in linear time, O(n). section 10.19 section 10.22
The method builds larger valid subheaps from smaller ones:
- Treat the arbitrary array as a binary, almost complete tree. Leaves already form valid subheaps. section 10.19
- Visit internal nodes from the lowest level upward, fixing each possible violation by pushing the node downward. section 10.19
- Prefer heapify over sorting or repeated insertion when the goal is simply to build a heap: those alternatives take O(n log n), while heapify takes O(n). section 10.19
Bottom-up repair
For an array represented as a binary tree, begin with the internal node at the second-to-last level. Its children are leaves, so pushing its root downward can produce a valid subheap. Continue upward until the root is repaired. section 10.19
def _heapify(self, elements):
self._elements = elements[:]
last_inner_node_index = self._first_leaf_index() - 1
for index in range(last_inner_node_index, -1, -1):
self._push_down(index)
def _first_leaf_index(self):
return len(self) // 2
A compact Python implementation copies the input array, finds the last internal node, and calls _push_down in reverse index order. section 10.19
