Build Heap from Array Heapify in DSA Go - 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.

intermediate

In the context of building a heap, why do we start heapify from the last non-leaf node?

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?

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

beginner

Explain the difference between 'heapify' and 'build heap'.

Heapify is the process of fixing the heap property at a single node, while build heap applies heapify repeatedly from bottom-up to build a heap from an entire array.

beginner

In Go, what data structure is commonly used to represent a heap when building it from an array?

A slice (dynamic array) is used to represent the heap, where parent and child relationships are determined by indices.

When building a max-heap from an array, which node index do you start heapifying from?

A Last non-leaf node

B Root node (index 0)

C Last leaf node

D Middle node

Heapify starts from the last non-leaf node because leaf nodes already satisfy the heap property.

What is the parent index of a node at index i in a zero-based array heap?

A i / 2

B 2 * i + 1

C 2 * i + 2

D (i - 1) / 2

In zero-based indexing, the parent of node i is at (i - 1) / 2.

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

A O(1)

B O(log n)

C O(n)

D O(n log n)

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

Which of the following best describes the build heap process?

A Heapify all non-leaf nodes from bottom to top

B Heapify all nodes from top to bottom

C Heapify all leaf nodes

D Sort the array first

Build heap heapifies all non-leaf nodes from bottom to top to ensure heap property.

After building a max-heap from the array [3, 1, 6, 5, 2, 4], what is the root element?

A 1

B 4

C 6

D 5

The max-heap root is the largest element, which is 6.

Describe the step-by-step process of building a max-heap from an unsorted array using heapify.

Think about fixing subtrees from bottom to top.

Explain why building a heap from an array using heapify is more efficient than inserting elements one by one.

Compare total time complexity of both methods.