Heapsort not working in Python for list of strings using heapq module
- by VSN
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
