I was reading the python 2.7 documentation when I came across the heapq module. I was interested in the heapify() and the heappop() methods. So, I decided to write a simple heapsort program for integers:

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

This worked like a charm.

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:

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

Note: I added a print statement in the for loop to see the heapified list.

Here's the output when I ran the script:

`$ 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']`

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.

Thanks, VSN