Teaching Kids Programming – How to Verify a Max Heap?

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a list of integers nums, return whether it represents a max heap. That is, for every i we have that:
nums[i] ≥ nums[2*i + 1] if 2*i + 1 is within bounds
nums[i] ≥ nums[2*i + 2] if 2*i + 2 is within bounds

Constraints
0 ≤ n ≤ 100,000 where n is the length of nums
Example 1
Input
nums = [4, 2, 3, 0, 1]
Output
True

Hints
Traverse in nums till childs are inbounds.

Algorithm to verify a max heap

A max heap is a binary tree that a parent is always bigger than its children. A min heap is the opposite that the parent is smaller than the children. A heap is a complete binary tree each level is fullfilled except the last/lowest level which should be partially ful-filled from left to right. We can store the heap in a list/array.

The left index of a parent i is i*2+1 and the right index of a parent i is i*2+2.

1
2
3
4
5
6
7
8
9

class Solution:
    def verifyMaxHeap(self, nums):
        n = len(nums)
        for i in range(n//2):
            if 2*i+1<n and nums[i] < nums[2 * i + 1]:
                return False
            if 2*i+2<n and nums[i] < nums[2 * i + 2]:
                return False
        return True

class Solution:
    def verifyMaxHeap(self, nums):
        n = len(nums)
        for i in range(n//2):
            if 2*i+1<n and nums[i] < nums[2 * i + 1]:
                return False
            if 2*i+2<n and nums[i] < nums[2 * i + 2]:
                return False
        return True

The time complexity is O(N) and space complexity is O(1) constant.

–EOF (The Ultimate Computing & Technology Blog) —