[neojiphre]

what's the best way to create a heap out of unsorted array? right now my code is not doing me any favors. the array is returned but not as a heap. when the number of items in the array is an odd number, the array is unchanged. anyone care to provide a working implementation so i can see which assumption used in my approach is wrong?

m = len(x)
  n = len(x)//2
  left = 2*n + 1
  right = 2*n + 2
  
  if left < m and x[left] <= x[n]:
    smallest = left
  else:
    smallest = n
    
  if right < m and x[right] <= x[smallest]:
    smallest = right
    
  if not largest == n:
    x[n], x[smallest] = x[smallest], x[n]
    heapify(x)

by the way the last call is just a recursive call of the function

[atraub]

Quote

anyone care to provide a working implementation so i can see which assumption used in my approach is wrong?

Nope! That's probably not going to happen.

Let's instead try to fix your code. What is the output you're getting, what is the output you should be getting?

[neojiphre]

atraub, on 04 October 2012 - 07:44 AM, said:

Quote

anyone care to provide a working implementation so i can see which assumption used in my approach is wrong?

Nope! That's probably not going to happen.

Let's instead try to fix your code. What is the output you're getting, what is the output you should be getting?

Nothing is changed for an array with an odd number of items for example . I should be getting a heap where the first item is smaller than the next two items, etc.

[neojiphre]

maybe someone would be kind enough to provide an algorithm/pseudocode on the correct way of turning an unsorted array into a heap? please? i don't understand where i have gone wrong...

[neojiphre]

figured it out, lock pl0x

[midknight51]

Care to share how you figured it out?