title: Shannon-Fano code as max-heap in python
body: <p>I have a min-heap code for Huffman coding which you can see here: <a href="http://rosettacode.org/wiki/Huffman_coding#Python" rel="nofollow">http://rosettacode.org/wiki/Huffman_coding#Python</a></p>
  
  <p>I'm trying to make a max-heap Shannon-Fano code which is similar to min-heap.</p>
  
  <p>Here is a code:</p>
  
  <pre><code>from collections import defaultdict, Counter
  import heapq, math
  
  def _heappop_max(heap):
  """Maxheap version of a heappop."""
  lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
  if heap:
      returnitem = heap[0]
      heap[0] = lastelt
      heapq._siftup_max(heap, 0)
      return returnitem
  return lastelt
  
  def _heappush_max(heap, item):
      """Push item onto heap, maintaining the heap invariant."""
      heap.append(item)
      heapq._siftdown_max(heap, 0, len(heap)-1)
  
  def sf_encode(symb2freq):
  heap = [[wt, [sym, ""]] for sym, wt in symb2freq.items()]
  heapq._heapify_max(heap)
  while len(heap) &gt; 1:
      lo = _heappop_max(heap)
      hi = _heappop_max(heap)
      for pair in lo[1:]:
          pair[1] = '0' + pair[1]
      for pair in hi[1:]:
          pair[1] = '1' + pair[1]
      _heappush_max(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
  print heap
  return sorted(_heappop_max(heap)[1:], key=lambda p: (len(p[1]), p))
  </code></pre>
  
  <p>But i've got output like this:</p>
  
  <pre><code>Symbol  Weight  Shannon-Fano Code
  !   1   1
  3   1   01
  :   1   001
  J   1   0001
  V   1   00001
  z   1   000001
  E   3   0000001
  L   3   00000001
  P   3   000000001
  N   4   0000000001
  O   4   00000000001
  </code></pre>
  
  <p>Am I right using heapq to implement Shannon-Fano coding? The problem in this string:</p>
  
  <pre><code>_heappush_max(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
  </code></pre>
  
  <p>and I don't understand how to fix it.</p>
  
  <p>Expect output similar to Huffman encoding</p>
  
  <pre><code>Symbol  Weight  Huffman Code
      2875    01
  a   744 1001
  e   1129    1110
  h   606 0000
  i   610 0001
  n   617 0010
  o   668 1000
  t   842 1100
  d   358 10100
  l   326 00110
  </code></pre>
  
  <p>Added:</p>
  
  <p>Well, I've tried to do this without heapq, but have unstopable recursion:</p>
  
  <pre><code>def sf_encode(iA, iB, maxP):
  global tupleList, total_sf
  global mid
  maxP = maxP/float(2)
  sumP = 0    
  for i in range(iA, iB):
      tup = tupleList[i]
      if sumP &lt; maxP or i == iA: # top group
          sumP += tup[1]/float(total_sf)
          tupleList[i] = (tup[0], tup[1], tup[2] + '0')
          mid = i           
      else: # bottom group
          tupleList[i] = (tup[0], tup[1], tup[2] + '1')
  print tupleList
  if mid - 1 &gt; iA:
      sf_encode(iA, mid - 1, maxP)
  if iB - mid &gt; 0:
      sf_encode(mid, iB, maxP)
  return tupleList
  </code></pre>