1. Senior Member
Join Date
Jan 2012
Posts
142
Rep Power
0

## heap sort question

Can someone explain how the heap-sort algorithm would work on the sequence (16,4,8,10,12).

with explanations of when the insertion and removal to the heaps are required and how they work.

I cannot find anything useful online regarding this.

2. Senior Member
Join Date
Jan 2012
Posts
142
Rep Power
0

## Re: heap sort question

anyone?

3. Senior Member
Join Date
Jan 2012
Posts
142
Rep Power
0

noone

4. ## Re: heap sort question

That is absolutely not how this works. This isn't google or a homework service. How do you think heap sort works? What have you tried? Where are you stuck?

5. Senior Member
Join Date
Jan 2012
Posts
142
Rep Power
0

## Re: heap sort question

yes I've tried. I don't understand how to begin it. Do I begin it in the tree or can I put them one by one using the insertion sort?

6. ## Re: heap sort question

Do you understand how heap sort works? If so, list the steps it takes and then apply those steps to your input. If not, do a google search of heap sort. I'm sure your class book is another valuable resource for an explanation.

7. ## Re: heap sort question

I wrote a blog article on heap sort once (check the button near the top of this page). Heap sort works with two passes (or phases); the first phase constructs a heap out of a sequence of items and the second phase removes the largest element from the heap and corrects it again until the heap is empty. A big advantage is that it can do this all in place (no auxiliary memory is needed) and it can do it stable big-Oh wise.

kind regards,

Jos

8. Senior Member
Join Date
Jan 2012
Posts
142
Rep Power
0

## Re: heap sort question

the way i was taught is that in the second phase it removes the smallest numbers first

9. ## Re: heap sort question

Originally Posted by stuckonjava
the way i was taught is that in the second phase it removes the smallest numbers first
Either one works, because a heap can be a min-heap or a max-heap. I think most descriptions use a max-heap. The idea is the same though. But these little discrepancies are why I asked you to define heap sort's behavior. If you know how you've been taught, where exactly are you stuck?

10. Senior Member
Join Date
Jan 2012
Posts
142
Rep Power
0

## Re: heap sort question

I understand the heap sort perfectly, the problem I have is showing the first phase in terms of the list. For eg the list (16,4,8,10,12). How would I show the first phase of this step by step. I can do it using a binary tree but whats the best way to present this without one?

11. ## Re: heap sort question

If you understand heap sort perfectly, I don't know what you're confused about. What is step one in heap sort? What is the first thing that would be done with that input?

12. Senior Member
Join Date
Jan 2012
Posts
142
Rep Power
0

## Re: heap sort question

ok the first thing would be to put 16 as the root, then the 4 as its left child, but as 4 is smaller than 16 they swap. The 8 would now become the right child of 4, the 10 would become the left child of 16 and swap places with it. The 12 would then become the right child of 10.

13. ## Re: heap sort question

If that's the way you were taught, okay. Like I said, most descriptions reverse that.

So what comes next?

14. Senior Member
Join Date
Jan 2012
Posts
142
Rep Power
0

## Re: heap sort question

the 4 would be put into the new sorted list(forgot what it is called), and 12 becomes the new root , the 12 and 8 now swap places making 8 the new root. The 8 is nwow put into the new list along wth the 4. 16 now becomes the root, and swaps places with 10 which is then sent into the list with 4 and 8. 12 becomes the new root and is sent into the list with 4,8,10. Now only 16 is left and as there is nothing to compare it with it is sent into the sorted list whose contents now consist of 4,8,10,12,16.

15. ## Re: heap sort question

Actually, I think the extraction is a little more involved than 12 magically becoming the new root. In the descriptions I'm familiar with, the last child is swapped with the root and then the old root is removed, and the new root is "trickled down" to maintain the heap.
Last edited by KevinWorkman; 03-15-2012 at 03:49 PM.

16. Senior Member
Join Date
Jan 2012
Posts
142
Rep Power
0

## Re: heap sort question

Oh, my description was that once the smallest key is the root it is remove into the new list.

17. ## Re: heap sort question

If that's your description, okay, but I'm working from the description I've been familiar with, which is also on wikipedia: Heapsort - Wikipedia, the free encyclopedia

A possible minimum is temporarily set as the root, but only to extract the actual root, which is the max. It could be that your teacher is taking a slightly different approach with heap sort, or it could be that you're misunderstanding a step to mean that the heap is a min-heap. I can't be sure which one is the case.

18. Senior Member
Join Date
Jan 2012
Posts
142
Rep Power
0

## Re: heap sort question

I though one of the heap rules was that node(v) >= node(v).parent

19. ## Re: heap sort question

Like I said, it really depends on the details of your implementation. There is a chance you're being given a slightly modified heap sort that uses the same idea in a different way. But the "traditional" approach to heap sort is to use a max-heap, where a parent is greater than any of its children (so the opposite of what you're saying). I'm not in your class though, so I really can't say for certain whether that's the case or you're simply confusing something.

Either way though, you're going to want to more fully understand what happens when you take the root out of your heap.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•