title: Heapsort not working in Python for list of strings using heapq module
body: <p>I was reading the python 2.7 documentation when I came across the <code>heapq</code> module. I was interested in the heapify() and the heappop() methods. So, I decided to write a simple heapsort program for integers:</p>
  
  <pre><code>from heapq import heapify, heappop
  
  user_input = raw_input("Enter numbers to be sorted: ")
  data = map (int, user_input.split(","))
  new_data = []
  
  for i in range(len(data)):
      heapify(data)
      new_data.append(heappop(data))
  
  print new_data
  </code></pre>
  
  <p>This worked like a charm.</p>
  
  <p>To make it more interesting, I thought I would take away the integer conversion and leave it as a string. Logically, it should make no difference and the code should work as it did for integers:</p>
  
  <pre><code>from heapq import heapify, heappop
  user_input = raw_input("Enter numbers to be sorted: ")
  data = user_input.split(",")
  new_data = []
  
  for i in range(len(data)):
      heapify(data)
      print data
      new_data.append(heappop(data))
  
  print new_data
  </code></pre>
  
  <p>Note: I added a print statement in the for loop to see the heapified list.<br><br>
  Here's the output when I ran the script:</p>
  
  <pre><code>`$ python heapsort.py 
  Enter numbers to be sorted: 4, 3, 1, 9, 6, 2
  [' 1', ' 3', ' 2', ' 9', ' 6', '4']
  [' 2', ' 3', '4', ' 9', ' 6']
  [' 3', ' 6', '4', ' 9']
  [' 6', ' 9', '4']
  [' 9', '4']
  ['4']
  [' 1', ' 2', ' 3', ' 6', ' 9', '4']`
  </code></pre>
  
  <p>The reasoning I applied was that since the strings are being compared, the tree should be the same if they were numbers. As is evident, the heapify didn't work correctly after the third iteration. Could someone help me figure out if I am missing something here? I'm running Python 2.4.5 on RedHat 3.4.6-9.</p>
  
  <p>Thanks,
  VSN</p>