Build Heap from Array Heapify in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main purpose of the heapify process when building a heap from an array?

Heapify rearranges elements to satisfy the heap property, ensuring each parent node is greater (max-heap) or smaller (min-heap) than its children.

beginner

In a zero-based array representation of a heap, what is the formula to find the left child index of a node at index i?

Left child index = 2 * i + 1

intermediate

Why do we start heapifying from the last non-leaf node when building a heap from an array?

Because leaf nodes already satisfy the heap property, starting from the last non-leaf node ensures all subtrees are heapified bottom-up efficiently.

intermediate

What is the time complexity of building a heap from an unsorted array using heapify?

O(n), where n is the number of elements in the array.

beginner

Explain the difference between max-heap and min-heap in the context of heapify.

In max-heap, heapify ensures parent nodes are greater than children. In min-heap, heapify ensures parent nodes are smaller than children.

What is the index of the last non-leaf node in a zero-based array of size n?

A Math.floor(n / 2) - 1

B n - 1

C Math.floor(n / 2)

D 0

The last non-leaf node is at index Math.floor(n / 2) - 1 because nodes after this index are leaves.

Which of the following best describes the heapify operation?

A Inserting a new element at the end

B Swapping elements to maintain heap property starting from a node downwards

C Sorting the entire array

D Removing the root element

Heapify fixes the heap property by swapping elements from a node down to its children.

What is the time complexity of heapify operation on a single node?

A O(n)

B O(n log n)

C O(1)

D O(log n)

Heapify on a single node takes O(log n) time because it may move down the height of the heap.

When building a heap from an array, why is the overall time complexity O(n) and not O(n log n)?

A Because heapify is called fewer times on nodes near the bottom which have smaller heights

B Because the array is already sorted

C Because heapify is a constant time operation

D Because only half the elements are heapified

Nodes near the bottom have smaller heights, so heapify takes less time on them, making total time O(n).

In a max-heap, after heapify, what can be said about the root node?

A It is the median element

B It is the smallest element in the heap

C It is the largest element in the heap

D It is the last inserted element

In a max-heap, the root node is always the largest element after heapify.

Describe step-by-step how to build a max-heap from an unsorted array using heapify.

Think about fixing the heap property from bottom to top.

Explain why heapify is more efficient when building a heap from an array compared to inserting elements one by one.

Compare bulk heap construction vs repeated insertions.