MEDIUM

DATA STRUCTURES AND ALGORITHMS

HEAPSTREES

Written By

Tom Wagner

Christopher Ang

Introduction Build a Max Heap

The Build Max Heap problem involves constructing a max heap from an array of integers. A max heap is a type of binary tree stored in an array that is organized such that the maximum value is always at the root of the tree. The solution to this problem must be able to rearrange the elements of the input array into a new array representing a max heap.

Problem Build a Max Heap

Given an array of integers, transform the array in-place to a max heap.

**Input:**
[1,2,3,4,5,6,7]

**Output:**

- [7,4,6,1,3,2,5] (sift up)

OR

- [7,5,6,4,2,1,3] (sift down)

**Input:**
[4,6,52,10,17,28,39,43,11]

**Output:**

- [52,43,39,17,10,6,28,4,11] (sift up)

OR

- [52,43,39,11,17,28,4,10,6] (sift down)

**Constraints**

`1 <= len(arr) <= 10,000`

- Every integer in the array will be <= 64-bits

Solution Build a Max Heap

Watch Someone Solve Build a Max Heap

Google InterviewJava Interview

Advance this person to the next round?

Technical Skills:

3/4

Problem Solving Ability:

1/4

Communication Ability:

3/4

Show Transcript

Watch more mock interviews

Max (or min) heaps are complete binary trees which satisfy the heap property, meaning each node is at least as large (or small) as each of its children. Max heaps can be encoded in arrays, where:

- The leftmost element of the array is the largest in the array
- The children of the node at index
`i`

are located at`2*i+1`

and`2*i+2`

To demonstrate this, consider the following max heap: [7, 5, 6, 4, 2, 1, 3].

Within this array, you can see the two children of `7`

(the `0th`

index element) at the following indexes: 2 * 0 + 1 = 1, and 2 * 0 + 2 = 2.

Additionally, for `5`

(the `1st`

index element) you can use the equation again to find its children at indexes: 2 * 1 + 1 = 3, and 2 * 1 + 2 = 4.

Given an arbitrary array, it is possible to reorder the elements such that they satisfy the above properties.

**Note:** Given a collection of integers, there may be many valid orderings that satisfy the min- or max-heap property, which will depend on the algorithm used to “heapify” the array.

Two common approaches to “heapifying” an array are to rely on sifting nodes up the tree, and sifting nodes down the tree.

To sift a node up the tree, we swap a node that is **larger** than its parent with its parent, and continue doing this (via e.g. recursion) until it is no larger than its parent.

To solve this problem using the “sift up” approach, we can use algebra to modify the equation we use to find a node’s children. Consider the following equation and note how it can be adjusted to solve for the parent node’s index:

```
child_one_idx = parent_idx * 2 + 1
child_two_idx = parent_idx * 2 + 2
```

Using algebra to isolate `parent_idx`

yields the following:

```
(child_one_idx + 1) / 2 = parent_idx
(child_two_idx + 2) / 2 = parent_idx
```

Note we now have two separate equations to find the parent index. Specifically, if we use the formula for child one on a node which is the second child, we will end up with a value that is `0.5`

larger than the actual parent index. So we need to find one equation that will work in all circumstances, and to accomplish this we can modify our `parent_idx`

equation slightly by using Math.floor():

```
parent_index = floor((i - 1 )/ 2)
```

To build the heap via sifting up involves starting at the **beginning** of the tree (head of the array), and iteratively sifting up each node. As the algorithm proceeds, nodes to the left of the current index will form a max heap, until finally all nodes have been sifted up.

```
from math import floor
def build_heap_siftup(arr):
# Skip the first element, since it has no parent
for i in range(1, len(arr)):
siftup(arr, i)
def siftup(arr, index):
if index < 1:
return
parent_idx = floor((index-1)/2)
# is the current node larger than its parent?
if arr[parent_idx] < arr[index]:
# we're larger, swap and check if we're larger than the next parent
swap(arr, parent_idx, index)
siftup(arr, parent_idx)
def swap(arr, first, second):
tmp = arr[first]
arr[first] = arr[second]
arr[second] = tmp
```

```
1from math import floor
2
3def build_heap_siftup(arr):
4 # Skip the first element, since it has no parent
5 for i in range(1, len(arr)):
6 siftup(arr, i)
7
8def siftup(arr, index):
9 if index < 1:
10 return
11 parent_idx = floor((index-1)/2)
12 # is the current node larger than its parent?
13 if arr[parent_idx] < arr[index]:
14 # we're larger, swap and check if we're larger than the next parent
15 swap(arr, parent_idx, index)
16 siftup(arr, parent_idx)
17
18def swap(arr, first, second):
19 tmp = arr[first]
20 arr[first] = arr[second]
21 arr[second] = tmp
```

- Time complexity:
`O(n * log(n))`

. This algorithm needs to call`siftUp()`

on all but the root node (the`n`

term), and needs to move each node to the top of the heap (which takes worst-case`log(n)`

time). Hence the`O(n * log(n))`

time complexity. - Space complexity:
`O(n)`

Conversely, we can also “heapify” an array by shifting smaller nodes down the tree.

To sift a node down the tree, we swap a node that is **smaller** than its children with its largest child, and continue doing so (via e.g. recursion) until it is no smaller than its children.

To build the heap via sifting down we start at the **end** and iteratively sifting down each node with the larger of its two children assuming at least one of them is bigger than the node itself. As the algorithm proceeds, nodes to the right of the current index will form max heaps.

Note this approach can also be applied to min heaps by sifting down nodes with children that are smaller than itself.

```
from math import floor
def build_heap_siftdown(arr):
# iterating right to left in the array
# we don't need to start strictly at the end, since those nodes have no children
# floor(len(arr)/2) gets the first node with children in a complete binary tree
for i in range(floor(len(arr)/2), -1, -1):
siftdown(arr, i)
def siftdown(arr, level=0):
if len(arr) <= 1:
return
left_idx = 2*level + 1
right_idx = 2*level + 2
largest = level
# See if the left child is larger
if left_idx < len(arr) and arr[left_idx] > arr[largest]:
largest = left_idx
# See if the right child is larger
if right_idx < len(arr) and arr[right_idx] > arr[largest]:
largest = right_idx
if largest != level:
# There's a child that's larger; switch with the largest child, and
# see if we're smaller than its children
swap(arr, largest, level)
siftdown(arr, largest)
def swap(arr, first, second):
tmp = arr[first]
arr[first] = arr[second]
arr[second] = tmp
```

```
1from math import floor
2
3def build_heap_siftdown(arr):
4 # iterating right to left in the array
5 # we don't need to start strictly at the end, since those nodes have no children
6 # floor(len(arr)/2) gets the first node with children in a complete binary tree
7 for i in range(floor(len(arr)/2), -1, -1):
8 siftdown(arr, i)
9
10def siftdown(arr, level=0):
11 if len(arr) <= 1:
12 return
13
14 left_idx = 2*level + 1
15 right_idx = 2*level + 2
16 largest = level
17
18 # See if the left child is larger
19 if left_idx < len(arr) and arr[left_idx] > arr[largest]:
20 largest = left_idx
21
22 # See if the right child is larger
23 if right_idx < len(arr) and arr[right_idx] > arr[largest]:
24 largest = right_idx
25
26 if largest != level:
27 # There's a child that's larger; switch with the largest child, and
28 # see if we're smaller than its children
29 swap(arr, largest, level)
30 siftdown(arr, largest)
31
32def swap(arr, first, second):
33 tmp = arr[first]
34 arr[first] = arr[second]
35 arr[second] = tmp
```

- Time complexity:
`O(n)`

- Space complexity:
`O(n)`

To see why the time complexity differs between these two approaches, see this stack overflow post: https://stackoverflow.com/a/18742428

MEDIUM

Data Structures and Algorithms

Three Sum

Given an array of integers, return an array of triplets such that i != j != k and nums[i] + nums[j] + nums[k] = 0.

ARRAYSSORTINGHASH MAPSSEARCH

Watch 1 interview

EASY

Data Structures and Algorithms

Reverse Linked List

Given the head of a linked list, reverse the list and return the new head.

LINKED LISTS

Watch 2 interviews

MEDIUM

Data Structures and Algorithms

Container With Most Water

Given n non-negative integers, find two lines that form a container that can hold the most amount of water.

GRAPH THEORYARRAYSSEARCHSORTING

Watch 1 interview

interviewing.io is a **mock interview practice platform**. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.

Ready to practice with a mock interview?

Book mock interviews with engineers from Google, Facebook, Amazon, or other top companies. Get detailed feedback on exactly what you need to work on. Everything is fully anonymous.