0
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)

Output which i got so far: Input 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]

the size of the List is : 4

In 1 iteration

[5, 8, 2, 6]

In 0 iteration

[8, 6, 2, 5]

heapified array is : [8, 6, 2, 5]

Sorted Array in Descending order [8]

vr22
  • 57
  • 3
  • 13
  • Hi @vr22 - you need to include details of the specific problem you are facing, otherwise people won't be able to give you a useful answer. – robjohncox Jul 03 '13 at 06:42
  • i need to find the next element from that particular list where maximum element is available.In this case maximum element is 8 and it means i need to take the element 22 from the list and add it at the position of 8,then adjuct heap accordingly – vr22 Jul 03 '13 at 06:52
  • I'm very confused by the question. You say you want to do a "k-way merge sort" but then you mention that you're heapifying your arrays as if you're going to do a heap sort. What algorithm are you trying to implement? Merge sort? Heap sort? Something else? – OmnipotentEntity Jul 03 '13 at 06:59
  • Am trying to implement k-way merge sort in this manner 1) Building maxheap taking first element from all sub-list 2)Take the root element and place it in final array 3)insert new root by taking the next element from the list where the previous root resides and adjuct heap.repeat the above process to get the sorted array in descending order – vr22 Jul 03 '13 at 07:11
  • could you use `heapq.merge()`? Here's [an example](http://stackoverflow.com/a/16954837/4279) – jfs Jul 03 '13 at 07:34
  • Am new to python and trying to implement this algorithm without using library function to get better insights – vr22 Jul 03 '13 at 07:42

0 Answers0