Is there a Python method to check whether a binary tree is a min heap?

Question

How can I write a function that can accept a binary tree as a parameter and returns True if it is a min heap and False if not.

from heapq import heapify

def binary_heap(tree):
  while len(tree) > 1:
    if heapify(tree):
        return True
    else:
        return False

Answer 1

Since a min heap has to satisfy, per heapq's documentation:

heap[k] <= heap[2*k+1] and heap[k] <= heap[2*k+2]

You can iterate through all child nodes to validate that they are greater than or equal to their parent nodes (note that i - 1 >> 1 is a shorthand for (i - 1) // 2 when i > 0):

def is_minheap(lst):
    return all(lst[i] >= lst[i - 1 >> 1] for i in range(1, len(lst)))

so that:

from heapq import heapify
from random import sample

lst = sample(range(10), 10)
print(is_minheap(lst), lst)
heapify(lst)
print(is_minheap(lst), lst)

outputs something like:

False [1, 2, 6, 8, 0, 5, 3, 9, 7, 4]
True [0, 1, 3, 7, 2, 5, 6, 9, 8, 4]

Demo: https://ideone.com/1uhd6c

Answer 2

For a binary tree to be a min heap, it should satisfy this two condition:

1. tree should be complete binary tree
2. every node should be less than or equal to its children

And a simple implementation would be like this

def is_min_heap(node,ind,total_nodes):
  if node is Node:
    return True
  if ind >= total_nodes:
    return False
  if node.left and node.val > node.left.val or node.right and node.val > node.right.val:
    return False
  return is_min_heap(node.left, 2 * ind + 1, total_nodes) and is_min_heap(node.right, 2 * ind + 2, total_nodes)