Is Min Heap Function


I want to write a function that tells me whether a given list is a min heap.

What I have written so far:

def is_min_heap(L): return _is_min_heap(L, 0) def _is_min_heap(L, i): if #base case else: return (L[i] < L[2*i+1] and _is_min_heap(L, 2*i+1)) and (L[i] < L[2*i+2] and _is_min_heap(L, 2*1+2))

I am not sure what the base case should be and is my recursive calls correct?

Also how can you control that the indexes are not eventually out of range?


You have three different cases for a given i: Either you have two children, in which case you need to check the heap property for both children and also recursively check both subtrees; or you have just a left children, in which case you just have to check that one; or you have no children, i.e. i is a leaf, which is always a valid heap by itself.

You can check the existence of a children by checking if its index is still in range with the list.

def _is_min_heap(L, i): l, r = 2 * i + 1, 2 * i + 2 if r < len(L): # has left and right children if L[l] < L[i] or L[r] < L[i]: # heap property is violated return False # check both children trees return _is_min_heap(L, l) and _is_min_heap(L, r) elif l < len(L): # only has left children if L[l] < L[i]: # heap property is violated return False # check left children tree return _is_min_heap(L, l) else: # has no children return True


  • Update web.config file in asp.net
  • How to put all my selected columns into a dummy variable?
  • Using bitbake is it possible to have a different do_install for a package based on the target image?
  • Get an index of a sorted matrix
  • Recursion in ASP.NET Core Razor views
  • mysql and indexes with more than one column
  • Can I use worksheet_change for a specific column only?
  • Cassandra 2.1: Recursion by nesting UDT's
  • @tailrec why does this method not compile with 'contains a recursive call not in tail position&
  • Java Application vs. Java Desktop Application in Netbeans [duplicate]
  • Primefaces lazy datascroller calling load twice
  • Find JSON nested nodes using multiple string values
  • passing a default argument to a browserify module
  • Getting unused unique values on a SQL table
  • Cloud Code function running twice
  • Image map in Flex
  • Spring: No transaction manager has been configured
  • Pycharm: Marking a folder as 'sources root' is not recursive for subfolders
  • accepts_nested_attributes_for practical form use for in Rails 3
  • Implicit joins and Where in Doctrine - how?
  • Web.config system.webserver errors
  • Object and struct member access and address offset calculation
  • How to write order and limit within cakephp joins array
  • Bug in WPF DataGrid
  • Does CUDA 5 support STL or THRUST inside the device code?
  • How to make Safari send if-modified-since header?
  • jQuery tmpl and DataLink beta
  • How can I estimate amount of memory left with calling System.gc()?
  • Function pointer “assignment from incompatible pointer type” only when using vararg ellipsis
  • 0x202A in filename: Why?
  • How to pass list parameters for each object using Spring MVC?
  • PHP: When would you need the self:: keyword?
  • Setting background image for body element in xhtml (for different monitors and resolutions)
  • File not found error Google Drive API
  • How to get Windows thread pool to call class member function?
  • JaxB to read class hierarchy
  • costura.fody for a dll that references another dll
  • Observable and ngFor in Angular 2
  • UserPrincipal.Current returns apppool on IIS
  • java string with new operator and a literal