heap sort question

**stuckonjava** · 03-15-2012, 12:35 AM

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.

**stuckonjava** · 03-15-2012, 01:42 AM

anyone?

**stuckonjava** · 03-15-2012, 01:16 PM

noone

**KevinWorkman** · 03-15-2012, 01:25 PM

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?

**stuckonjava** · 03-15-2012, 01:37 PM

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?

**KevinWorkman** · 03-15-2012, 01:43 PM

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.

**JosAH** · 03-15-2012, 01:51 PM

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

**stuckonjava** · 03-15-2012, 01:54 PM

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

**KevinWorkman** · 03-15-2012, 01:58 PM

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?

**stuckonjava** · 03-15-2012, 02:09 PM

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?

**KevinWorkman** · 03-15-2012, 02:15 PM

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?

**stuckonjava** · 03-15-2012, 02:25 PM

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.

**KevinWorkman** · 03-15-2012, 02:32 PM

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

So what comes next?

**stuckonjava** · 03-15-2012, 02:41 PM

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.

**KevinWorkman** · 03-15-2012, 02:47 PM

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.

**stuckonjava** · 03-15-2012, 02:55 PM

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

**KevinWorkman** · 03-15-2012, 02:58 PM

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.

**stuckonjava** · 03-15-2012, 03:06 PM

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

**KevinWorkman** · 03-15-2012, 03:18 PM

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.