5 Replies - 657 Views - Last Post: 05 October 2012 - 12:46 AM Rate Topic: -----

#1 neojiphre  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 17
  • Joined: 27-October 11

best way to create a heap out of unsorted array

Posted 04 October 2012 - 02:16 AM

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

Is This A Good Question/Topic? 0
  • +

Replies To: best way to create a heap out of unsorted array

#2 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 756
  • View blog
  • Posts: 1,990
  • Joined: 23-December 08

Re: best way to create a heap out of unsorted array

Posted 04 October 2012 - 07:44 AM

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?
Was This Post Helpful? 0
  • +
  • -

#3 neojiphre  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 17
  • Joined: 27-October 11

Re: best way to create a heap out of unsorted array

Posted 04 October 2012 - 11:12 AM

View Postatraub, 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.
Was This Post Helpful? 0
  • +
  • -

#4 neojiphre  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 17
  • Joined: 27-October 11

Re: best way to create a heap out of unsorted array

Posted 04 October 2012 - 05:20 PM

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...
Was This Post Helpful? 0
  • +
  • -

#5 neojiphre  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 17
  • Joined: 27-October 11

Re: best way to create a heap out of unsorted array

Posted 05 October 2012 - 12:27 AM

figured it out, lock pl0x
Was This Post Helpful? 0
  • +
  • -

#6 midknight51  Icon User is offline

  • New D.I.C Head

Reputation: 20
  • View blog
  • Posts: 47
  • Joined: 25-September 12

Re: best way to create a heap out of unsorted array

Posted 05 October 2012 - 12:46 AM

Care to share how you figured it out?
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1