title: Building MIN-HEAP in Python
body: <p>I've got to build a complete MIN-HEAP implementation in Python, without using built-in heap functions.</p>
  
  <p>So I've got definitions of parent, left child and right child, which take in account that python number list elements from 0:</p>
  
  <pre><code>from random import randint
  import math 
  
  def parent(i):
      x = int(l.index(l[i])) #########3
      y = int(math.floor(x/2))
      return y-1  
  
  def lchild(i):
      x = int(l.index(l[i]))
      y = int(math.floor(x*2))
      return y-1
  
  def rchild(i):
      x = int(l.index(l[i]))
      y = int(math.floor(x*2 + 1))
      return y-1
  </code></pre>
  
  <p>then I have a part of code that generates (pseudo)random list for me into the list <strong>l</strong>:</p>
  
  <pre><code>l = []
  dl = int(input)
  
  for i in range (0, dl):
      x = int(randint(1,100)) 
      l.append(x)             
  </code></pre>
  
  <p>and until this point everything works good. then I have a function bkop for making the table <strong>l</strong> into a min-heap.</p>
  
  <pre><code>def bkop(l):
          j = 0
          for i in range(0, len(l)):
                  if int(l[i]) &lt; int(parent(l[i])): #########2
                          l[i], l[parent(i)] = l[parent(i)], l[i]
                          j = j+1
                  if j != 0:
                          bkop(l)
  </code></pre>
  
  <p>then I want to run a program and see the results:</p>
  
  <pre><code>bkop(l) #########1
  print l
  </code></pre>
  
  <p>The program crashes with an error <strong>list index out of range</strong> pointing to the 3 lines, that i've marked with #########. I've started writing this about a month ago and i'm pretty sure, that parent, lchild and rchild worked at that time. Do you know, what's wrong?</p>
  
  <p>EDIT1:
  Ok, so I've fixed the parent/lchild/rchild definitions. I've checked, they return correct values. Here is the code:</p>
  
  <pre><code>def parent(i):
      x = i + 1
      y = x//2
      return y-1
  
  def lchild(i):
      x = i + 1
      y = x*2
      return y-1
  
  def rchild(i):
      x = i + 1
      y = x*2 + 1
      return y-1
  </code></pre>
  
  <p>The function generating random list is pretty much intact. Then I have this bkop function (that makes a min-heap out of the <strong>l</strong> list). I use print before and after on purpose, to se if it works... and it doesn't. It returns the same list both times, no compile errors or anything. Any idea how to fix it?</p>
  
  <pre><code>print(l)
  def bkop(l): 
          j = 0
          for i in range(0, len(l)):
                  if l[i] &lt; parent(i):
                          l[i], l[parent(i)] = l[parent(i)], l[i]
                          j = j+1
                  if j != 0:
                          bkop(l)
  bkop(l)
  print l
  </code></pre>
  
  <p>EDIT2: 
  Ok, so I've fixed <strong>bkop</strong> as you've suggested:</p>
  
  <pre><code>print bkop(l)
  def bkop(l):
          j = 0
          for i in range(1, len(l)):
                  if l[i] &lt; l[parent(i)]:
                          l[i], l[parent(i)] = l[parent(i)], l[i]
                          j = j+1
                  if j != 0:
                          bkop(l)
  bkop(l)
  print bkop(l)
  </code></pre>
  
  <p>But when I run it, I get this first a randomly-generated table (as I should), and instead of a min-heap table, I get <strong>None</strong> value, as below:</p>
  
  <pre><code>[34, 9, 94, 69, 77, 33, 56]
  None
  </code></pre>
  
  <p>Any ideas? Maybe I should do it another way around, not comparing l[i] to parent, but l[i] to it's left and right children?</p>