Given an array A of size N, the task is to check if the given array represents a Binary Max Heap.
Example 1:
Input:  arr[] = {90, 15, 10, 7, 12, 2}
Output: True
The given array represents below tree
       90
     /    \
   15      10
  /  \     /
7    12  2
The tree follows max-heap property as every
node is greater than all of its descendants.
Example 2:
Input:  arr[] = {9, 15, 10, 7, 12, 11}
Output: False
The given array represents below tree
       9
     /    \
   15      10
  /  \     /
7    12  11
The tree doesn't follows max-heap property 9 is
smaller than 15 and 10, and 10 is smaller than 11. 
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function isMaxHeap() which takes the array A[] and its size N as inputs and returns  "1", else print "0" (without quotes).
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
 
Constraints:
1 ≤ N ≤ 10^{6}
1 ≤ A_{i} ≤ 10^{15}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Range queries

Starter code: 
class Solution:
    def arrayRepresentHeap(self,arr,n):
        # Your code goes here            


Solutions:
from queue import Queue

class Solution:

	def arrayRepresentHeap(self, arr, n):
		if not arr:
			return 1
		seen = False
		for i in range(n):
			left = i * 2 + 1
			right = left + 1
			if left <= n - 1:
				if seen or arr[left] > arr[i]:
					return 0
			else:
				seen = True
			if right <= n - 1:
				if seen or arr[right] > arr[i]:
					return 0
			else:
				seen = True
		return 1


class Solution:

	def arrayRepresentHeap(self, arr, n):
		for i in range(n - 1, 0, -1):
			if arr[i] > arr[(i - 1) // 2]:
				return 0
		return 1


class Solution:

	def arrayRepresentHeap(self, arr, n):
		for i in range(n):
			l = i * 2 + 1
			r = i * 2 + 2
			if l < n and arr[l] > arr[i]:
				return 0
			if r < n and arr[r] > arr[i]:
				return 0
		return 1


class Solution:

	def arrayRepresentHeap(self, arr, n):
		i = 0
		if len(arr) == 1 or len(arr) == 0:
			return 1
		while 2 * i + 2 <= len(arr):
			if arr[i] < arr[2 * i + 1]:
				return 0
			if 2 * i + 2 < len(arr) and arr[i] < arr[2 * i + 2]:
				return 0
			i += 1
		return 1


class Solution:

	def arrayRepresentHeap(self, arr, n):
		for i in range(n):
			left = 2 * i + 1
			right = 2 * i + 2
			if left < n and arr[i] < arr[left]:
				return 0
			if right < n and arr[i] < arr[right]:
				return 0
		return 1


class Solution:

	def arrayRepresentHeap(self, arr, n):
		if n == 2:
			if arr[0] > arr[1]:
				return 1
			return 0
		ans = True
		for i in range(1, n):
			parent = (i + 1) // 2 - 1
			if arr[parent] < arr[i]:
				ans = False
				break
		return 1 if ans == True else 0


class Solution:

	def arrayRepresentHeap(self, arr, n):

		def parent(i):
			return (i - 1) // 2
		for child in range(1, n):
			if not arr[parent(child)] > arr[child]:
				return 0
		return 1


class Solution:

	def __init__(self):
		self.arr = None

	def arrayRepresentHeap(self, arr, n):
		self.arr = arr
		return int(self.checkMaxHeap(0))

	def checkMaxHeap(self, idx):
		if idx >= len(self.arr):
			return True
		boolean = True
		child_idx1 = 2 * idx + 1
		if child_idx1 < len(self.arr):
			if self.arr[idx] < self.arr[child_idx1]:
				return False
			else:
				boolean = boolean and self.checkMaxHeap(child_idx1)
		if not boolean:
			return boolean
		child_idx2 = 2 * idx + 2
		if child_idx2 < len(self.arr):
			if self.arr[idx] < self.arr[child_idx2]:
				return False
			else:
				return self.checkMaxHeap(child_idx2)
		return True


class Solution:

	def arrayRepresentHeap(self, a, n):
		x = (n - 2) // 2 + 1
		for i in range(x):
			if a[2 * i + 1] > a[i]:
				return 0
			if 2 * i + 2 < n and a[2 * i + 2] > a[i]:
				return 0
		return 1


class Solution:

	def arrayRepresentHeap(self, arr, n):
		for child_index in range(n - 1, 0, -1):
			parent_index = child_index // 2 + child_index % 2 - 1
			if arr[child_index] > arr[parent_index]:
				return 0
		return 1


class Solution:

	def arrayRepresentHeap(self, arr, n):
		for index in range(n - 1, 0, -1):
			child_node = arr[index]
			parent_node = arr[index // 2 if index % 2 == 1 else (index - 1) // 2]
			if child_node > parent_node:
				return 0
		return 1


class Solution:

	def arrayRepresentHeap(self, arr, n):
		if n == 1:
			return 1
		if n == 2:
			if arr[0] > arr[1]:
				return 1
			else:
				return 0
		for i in range(int((n - 2) / 2 + 1)):
			if arr[i] < arr[2 * i + 1]:
				return 0
			if 2 * i + 2 < n and arr[i] < arr[2 * i + 2]:
				return 0
		return 1


class Solution:

	def arrayRepresentHeap(self, arr, n):
		heap = []
		i = 0
		while arr:
			heap.append(arr[:2 ** i])
			arr = arr[2 ** i:]
			i += 1
		for i in range(1, len(heap)):
			for (j, item) in enumerate(heap[i]):
				if item > heap[i - 1][j // 2]:
					return 0
		return 1


class Solution:

	def arrayRepresentHeap(self, arr, n):
		if self.built(arr) == True:
			return 1
		else:
			return 0

	def heapify(self, a, i, n):
		lr = i
		(l, r) = (2 * i + 1, 2 * i + 2)
		if l < n and a[l] > a[lr]:
			lr = l
			return False
		if r < n and a[r] > a[lr]:
			lr = r
			return False

	def built(self, arr):
		n = len(arr)
		for i in range(n // 2, -1, -1):
			y = self.heapify(arr, i, n)
			if y == False:
				return False
		return True


class Solution:

	def arrayRepresentHeap(self, arr, n):
		for i in range(n // 2 - 1, -1, -1):
			left_child = 2 * i + 1
			right_child = 2 * i + 2
			if left_child < n and arr[left_child] > arr[i]:
				return 0
			if right_child < n and arr[right_child] > arr[i]:
				return 0
		return 1


class Solution:

	def left(self, pos):
		return 2 * pos + 1

	def right(self, pos):
		return 2 * pos + 2

	def arrayRepresentHeap(self, arr, n):
		tag = 1
		for i in range(n // 2 + 1):
			if self.left(i) <= len(arr) - 1:
				if arr[i] < arr[self.left(i)]:
					tag = 0
			if self.right(i) <= len(arr) - 1:
				if arr[i] < arr[self.right(i)]:
					tag = 0
		return tag


import math

class Solution:

	def arrayRepresentHeap(self, arr, n):
		bit = 1
		for x in range(math.floor(n / 2)):
			if max(arr[bit:bit + 2]) > arr[x]:
				return 0
			bit += 2
		return 1


class Solution:

	def arrayRepresentHeap(self, arr, n):
		for i in range(n):
			lchild = 2 * i + 1
			rchild = 2 * i + 2
			if lchild < n and arr[lchild] > arr[i]:
				return 0
			if rchild < n and arr[rchild] > arr[i]:
				return 0
		return 1


class Solution:

	def arrayRepresentHeap(self, arr, n):
		for i in range(n):
			childL = 2 * i + 1
			childR = 2 * i + 2
			if childL < n and arr[childL] > arr[i]:
				return 0
			if childR < n and arr[childR] > arr[i]:
				return 0
		return 1


from math import ceil

class Solution:

	def arrayRepresentHeap(self, a, n):
		m = (n - 1) // 2
		for i in range(m + 1):
			if i * 2 + 1 < n:
				if a[i] < a[i * 2 + 1]:
					return 0
			if i * 2 + 2 < n:
				if a[i] < a[i * 2 + 2]:
					return 0
		return 1


class Solution:

	def arrayRepresentHeap(self, arr, n):
		middle = (n + 1) // 2
		for index in range(middle):
			leftIndex = index * 2 + 1
			rightIndex = index * 2 + 2
			if leftIndex < n:
				if arr[leftIndex] > arr[index]:
					return 0
			if rightIndex < n:
				if arr[rightIndex] > arr[index]:
					return 0
		return 1


class Solution:

	def arrayRepresentHeap(self, arr, n):
		for i in range(n):
			l_child = 2 * i + 1
			r_child = 2 * i + 2
			if l_child < n and arr[l_child] > arr[i]:
				return 0
			if r_child < n and arr[r_child] > arr[i]:
				return 0
		return 1


from math import inf

class Solution:

	def take(self, arr, n, ind):
		if ind < n:
			return arr[ind]
		return -inf

	def arrayRepresentHeap(self, arr, n):
		for x in range(n):
			al = 2 * x + 1
			if arr[x] < self.take(arr, n, 2 * x + 1) or arr[x] < self.take(arr, n, 2 * x + 2):
				return 0
		return 1


class Solution:

	def arrayRepresentHeap(self, arr, n):
		index = 0
		while index < n:
			parent = arr[index]
			(l, r) = (2 * index + 1, 2 * index + 2)
			if l < n and parent < arr[l]:
				return 0
			if r < n and parent < arr[r]:
				return 0
			index += 1
		return 1


import math

class Solution:

	def arrayRepresentHeap(self, arr, n):
		if n == 1:
			return 1
		if n == 2:
			if arr[0] < arr[1]:
				return 0
		_is_max_heap = 1
		for i in range(0, math.ceil(len(arr) / 2)):
			j = i * 2
			for _ in range(j + 1, j + 3):
				if _ < len(arr):
					if arr[i] < arr[_]:
						_is_max_heap = 0
						break
			if _is_max_heap == 0:
				break
		return _is_max_heap


import sys

class Solution:

	def arrayRepresentHeap(self, arr, n):
		for i in range(n):
			if 2 * i + 1 < n and arr[2 * i + 1] > arr[i]:
				return 0
			if 2 * i + 2 < n and arr[2 * i + 2] > arr[i]:
				return 0
		return 1


import heapq

class Solution:

	def arrayRepresentHeap(self, arr, n):
		hp = []
		for i in range(len(arr)):
			hp.append(arr[i])
			heapq._siftdown_max(hp, 0, len(hp) - 1)
			if hp[i] != arr[i]:
				return 0
		return 1


class Solution:

	def arrayRepresentHeap(self, arr, n):
		for i in range(n // 2 - 1, -1, -1):
			l = 2 * i + 1
			r = 2 * i + 2
			boo1 = True
			boo2 = True
			if l < n:
				if arr[i] < arr[l]:
					boo1 = False
			if r < n:
				if arr[i] < arr[r]:
					boo2 = False
			if not boo1 or not boo2:
				return 0
		return 1


class Solution:

	def _shiftup(self, arr, pos):
		end = len(arr)
		start_pos = pos
		item = arr[pos]
		flag = 0
		child_pos = 2 * pos + 1
		while child_pos < end:
			right_child_pos = child_pos + 1
			if right_child_pos < end and arr[right_child_pos] > arr[child_pos]:
				child_pos = right_child_pos
			if arr[child_pos] > arr[pos]:
				flag = 1
			pos = child_pos
			child_pos = 2 * pos + 1
		return flag

	def arrayRepresentHeap(self, arr, n):
		for i in reversed(range(len(arr) // 2)):
			flag = self._shiftup(arr, i)
			if flag:
				return 0
		return 1


class Solution:

	def arrayRepresentHeap(self, arr, n):
		for i in range(0, n):
			l = 2 * i + 1
			r = 2 * i + 2
			if n == 1:
				return 1
			if n < 3:
				if arr[i] > arr[l]:
					return 1
				else:
					return 0
			if l < n:
				if arr[i] > arr[l]:
					pass
				else:
					return 0
			if r < n:
				if arr[i] > arr[r]:
					pass
				else:
					return 0
		return 1


class Solution:

	def checkChildren(self, nodePos, arr):
		child1 = (nodePos + 1) * 2 - 1
		child2 = (nodePos + 1) * 2
		if child2 < len(arr):
			return arr[child1] <= arr[nodePos] and arr[child2] <= arr[nodePos]
		elif child1 < len(arr):
			return arr[child1] <= arr[nodePos]
		else:
			return True

	def arrayRepresentHeap(self, arr, n):
		for nodePos in range(n):
			if not self.checkChildren(nodePos, arr):
				return 0
		return 1


class Solution:

	def checkParent(self, arr, pos):
		if pos == 0:
			return True
		return arr[pos] < arr[(pos - 1) // 2]

	def arrayRepresentHeap(self, arr, n):
		for pos in range(len(arr)):
			if not self.checkParent(arr, pos):
				return 0
		return 1


class Solution:

	def arrayRepresentHeap(self, arr, n):
		for i in range((n - 1) // 2 + 1):
			left_index = 2 * i + 1
			right_index = 2 * i + 2
			if left_index < n and arr[i] < arr[left_index]:
				return 0
			elif right_index < n and arr[i] < arr[right_index]:
				return 0
		return 1


class Solution:

	def arrayRepresentHeap(self, arr, n):
		a = arr
		a.insert(0, 0)
		l = len(a)
		flag = 1
		i = 1
		while i < l // 2 + 1:
			j = 2 * i
			if j < l:
				if a[i] > a[j]:
					pass
				else:
					flag = 0
			if j + 1 < l:
				if a[i] > a[j + 1]:
					pass
				else:
					flag = 0
			i += 1
		if flag == 0:
			return 0
		else:
			return 1


class Solution:

	def arrayRepresentHeap(self, arr, n):
		for x in range(len(arr)):
			if 2 * x + 1 < len(arr):
				left_child = arr[2 * x + 1]
				if arr[x] < left_child:
					return 0
			if 2 * x + 2 < len(arr):
				right_child = arr[2 * x + 2]
				if arr[x] < right_child:
					return 0
		return 1


class Solution:

	def arrayRepresentHeap(self, arr, n):
		if len(arr) < 2:
			return 1
		arr.insert(0, 'NA')
		size = len(arr)
		for i in range(1, size):
			par = i
			LC = 2 * i
			RC = 2 * i + 1
			if LC >= size:
				break
			if LC < size and arr[par] < arr[LC] or (RC < size and arr[par] < arr[RC]):
				return 0
		return 1


class Solution:

	def arrayRepresentHeap(self, arr, n):

		def helper(i):
			if i >= n:
				return 1
			l = i * 2 + 1
			r = i * 2 + 2
			if l < n and arr[i] < arr[l]:
				return 0
			if r < n and arr[i] < arr[r]:
				return 0
			return helper(l) and helper(r)
		return helper(0)