Heapify an array into a max-heap
Company: Akuna Capital
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Take-home Project
Given the array [6, 15, 2, 4, 3, 8, 19], apply heapify to build a max-heap using the standard in-place bottom-up method with a 0-indexed array representation. What is the final array after heap construction? Show key steps or justify your result.
Quick Answer: This question evaluates understanding of heap data structures and the in-place bottom-up heapify algorithm for building a max-heap on a 0-indexed array, testing skills in array manipulation, heap invariants, and algorithmic reasoning.
Apply standard in-place bottom-up heapify to return a max-heap array.
Examples
Input: ([6, 15, 2, 4, 3, 8, 19],)
Expected Output: [19, 15, 8, 4, 3, 6, 2]
Explanation: Prompt array.
Input: ([1, 2, 3],)
Expected Output: [3, 2, 1]
Explanation: Small heap.
Input: ([],)
Expected Output: []
Explanation: Empty array.
Hints
- Sift down each internal node from right to left.