def left_child(i):
return 2*i+1
def right_child(i):
return 2*i+2
def kway_merge(elements):
Build_heap(elements)
sub_array_size = len(elements)
sort_Array = []
sort_Array.append(elements[0])
print "Sorted Array in Descending order", sort_Array
def heapify(nums,i,size):
l = left_child(i)
r = right_child(i)
if l <= size and r <= size:
if r != size:
if nums[l] >= nums[r]:
max_element = nums[l]
max_index = l
elif nums[l] <= nums[r]:
max_element = nums[r]
max_index = r
if nums[i] >= max_element:
print nums
return
elif nums[i] <= max_element:
nums[i],nums[max_index] = max_element,nums[i]
heapify(nums,max_index,size)
else:
nums[i],nums[l] = nums[l],nums[i]
print nums
def Build_heap(elements):
#actual_size = size*s
size = len(elements)
print "the size of the List is : %d " %size
iterate = size//2-1
for i in range(iterate,-1,-1):
print "In %d iteration" %i
heapify(elements,i,size)
print "heapified array is : " ,elements
if __name__ == '__main__':
nums = [[5,10,15,20],[6,3,16,9],[2,9,26,40],[8,22,23,24]]
print "Input array: ",nums
initial_array = []
for i in range(len(nums)):
initial_array.append(nums[i][0])
print initial_array
kway_merge(initial_array)
到目前为止我得到的输出：输入数组：
[[5, 10, 15, 20], [6, 3, 16, 9], [2, 9, 26, 40], [8, 22, 23, 24]]
[5]
[5, 6]
[5、6、2]
[5、6、2、8]
列表的大小是：4
在 1 次迭代中
[5、8、2、6]
在 0 次迭代中
[8、6、2、5]
heapified 数组是：[8, 6, 2, 5]
降序排列的数组 [8]