60735

Is Min Heap Function

Question:

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?

Answer1:

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

Recommend

  • 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