# best way to create a heap out of unsorted array

Page 1 of 1

## 5 Replies - 943 Views - Last Post: 05 October 2012 - 12:46 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=294213&amp;s=0f66fe5bf7db2cb9bf6b9ef7a9d59be7&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 neojiphre

Reputation: 0
• Posts: 20
• 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

• Pythoneer

Reputation: 760
• Posts: 2,015
• 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?

### #3 neojiphre

Reputation: 0
• Posts: 20
• Joined: 27-October 11

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

Posted 04 October 2012 - 11:12 AM

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.

### #4 neojiphre

Reputation: 0
• Posts: 20
• 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...

### #5 neojiphre

Reputation: 0
• Posts: 20
• 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

### #6 midknight51

Reputation: 20
• 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?