我写的堆排序代码如下:
有趣的是
self.first, self.last = self.last, self.first
不交换列表头部和尾部的两个值self.list
。
为什么?
#heapsort
import pdb
class heap(object):
def __init__(self, list):
super(heap, self).__init__()
self.list = list
self.heapify()
if self.list:
self.first = self.list[0]
self.last = self.list[len(self.list)-1]
def length(self):
return len(self.list)
def heap_node(self,i):
large_i = i
if 2*i+1<self.length() and self.list[2*i+1]>self.list[i]:
large_i = 2*i+1
if 2*i+2<self.length() and self.list[2*i+2]>self.list[large_i]:
large_i = 2*i+2
if large_i!=i:
self.list[large_i], self.list[i] = self.list[i], self.list[large_i]
self.heap_node(large_i)
def heapify(self):
for i in range(self.length()/2,0,-1):
j=i-1
self.heap_node(j)
def sort(self):
# pdb.set_trace()
if not self.list:
return []
else:
# self.list[0], self.list[len(self.list)-1] = self.list[len(self.list)-1], self.list[0]
self.first, self.last = self.last, self.first
return heap(self.list[0:(self.length()-1)]).sort() + [self.list[len(self.list)-1]]
h=heap([1,3,2,5,4])
print h.list
print h.sort()