title: What data structure to use for heap in python
body: <p>I was writing a custom heap implementation for <code>Udacity</code> course and needed a heap that would return a metric value for an element through both heap index and key of an element.</p>
  
  <p>I have ended up with a list for a heap that contains <code>tuples (Metric, Key)</code>.</p>
  
  <p>But to get the right element via key I had to create a separate map and maintain it's validity  for each change in the heap.</p>
  
  <p>So in the end instead of having functions with two parameters like <code>heapup(heap, i)</code>, I had to pass map to all the functions - <code>heapup(heap, i, map)</code>. </p>
  
  <p>I am wondering if there is a simpler way to do this through procedures, lists and dictionaries. Or Heap object will be required to hide the Map inside?</p>
  
  <pre><code> def heapup(L, i, map):
  
      if i == 0: return i # we reached the top!
      if i &gt;= len(L): return i
      if L[parent(i)] &gt; L[i]:
         # print "going up"
          (L[i], L[parent(i)]) = (L[parent(i)], L[i])
          map[L[i][1]] = i
          map[L[parent(i)][1]] = parent(i)
          return up_heapify(L, parent(i), map)
      else:
       #   print "going down"
          if leaf(L,i): return i
          if one_child(L,i): return i # we could only come this way
          if L[i] &gt; L[left(i)]: # compare with left child
              (L[i], L[left(i)]) = (L[left(i)], L[i])
              map[L[i][1]] = i
              map[L[left(i)][1]] = left(i)
              return left(i)
          if L[i] &gt; L[right(i)]: # compare with right child
              (L[i], L[right(i)]) = (L[right(i)], L[i])
              map[L[i][1]] = i
              map[L[right(i)][1]] = right(i)
              return right(i)
  </code></pre>
  
  <p>I would like to get rid of map in that function but still be able to get items values from heap by their key which I now can do like this:</p>
  
  <pre><code>item = heap[map[key]]
  </code></pre>
  
  <p><strong>For example:</strong></p>
  
  <p>if  </p>
  
  <pre><code>L = [(3,'A'), (5, 'D'), (4, 'G') ...] 
  </code></pre>
  
  <p>then</p>
  
  <pre><code>map = {'A':0, 'D':1, 'G': 2, ...} 
  </code></pre>
  
  <p>so I can get a value of an element like this: </p>
  
  <pre><code>L[map['G']] 
  </code></pre>
  
  <p>which will give me 4</p>