Results 1 to 19 of 19
Thread: heap sort question
 03152012, 01:35 AM #1Senior Member
 Join Date
 Jan 2012
 Posts
 151
 Rep Power
 5
 03152012, 02:42 AM #2Senior Member
 Join Date
 Jan 2012
 Posts
 151
 Rep Power
 5
Re: heap sort question
anyone?
 03152012, 02:16 PM #3Senior Member
 Join Date
 Jan 2012
 Posts
 151
 Rep Power
 5
Re: heap sort question
noone
 03152012, 02:25 PM #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?
How to Ask Questions the Smart Way
Static Void Games  GameDev tutorials, free Java and JavaScript hosting!
Static Void Games forum  Come say hello!
 03152012, 02:37 PM #5Senior Member
 Join Date
 Jan 2012
 Posts
 151
 Rep Power
 5
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?
 03152012, 02:43 PM #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.
How to Ask Questions the Smart Way
Static Void Games  GameDev tutorials, free Java and JavaScript hosting!
Static Void Games forum  Come say hello!
 03152012, 02:51 PM #7
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,321
 Blog Entries
 7
 Rep Power
 25
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 bigOh wise.
kind regards,
JosThe only person who got everything done by Friday was Robinson Crusoe.
 03152012, 02:54 PM #8Senior Member
 Join Date
 Jan 2012
 Posts
 151
 Rep Power
 5
Re: heap sort question
the way i was taught is that in the second phase it removes the smallest numbers first
 03152012, 02:58 PM #9
Re: heap sort question
Either one works, because a heap can be a minheap or a maxheap. I think most descriptions use a maxheap. 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?
How to Ask Questions the Smart Way
Static Void Games  GameDev tutorials, free Java and JavaScript hosting!
Static Void Games forum  Come say hello!
 03152012, 03:09 PM #10Senior Member
 Join Date
 Jan 2012
 Posts
 151
 Rep Power
 5
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?
 03152012, 03:15 PM #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?
How to Ask Questions the Smart Way
Static Void Games  GameDev tutorials, free Java and JavaScript hosting!
Static Void Games forum  Come say hello!
 03152012, 03:25 PM #12Senior Member
 Join Date
 Jan 2012
 Posts
 151
 Rep Power
 5
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.
 03152012, 03:32 PM #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?How to Ask Questions the Smart Way
Static Void Games  GameDev tutorials, free Java and JavaScript hosting!
Static Void Games forum  Come say hello!
 03152012, 03:41 PM #14Senior Member
 Join Date
 Jan 2012
 Posts
 151
 Rep Power
 5
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.
 03152012, 03:47 PM #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; 03152012 at 03:49 PM.
How to Ask Questions the Smart Way
Static Void Games  GameDev tutorials, free Java and JavaScript hosting!
Static Void Games forum  Come say hello!
 03152012, 03:55 PM #16Senior Member
 Join Date
 Jan 2012
 Posts
 151
 Rep Power
 5
Re: heap sort question
Oh, my description was that once the smallest key is the root it is remove into the new list.
 03152012, 03:58 PM #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 minheap. I can't be sure which one is the case.How to Ask Questions the Smart Way
Static Void Games  GameDev tutorials, free Java and JavaScript hosting!
Static Void Games forum  Come say hello!
 03152012, 04:06 PM #18Senior Member
 Join Date
 Jan 2012
 Posts
 151
 Rep Power
 5
Re: heap sort question
I though one of the heap rules was that node(v) >= node(v).parent
 03152012, 04:18 PM #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 maxheap, 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.How to Ask Questions the Smart Way
Static Void Games  GameDev tutorials, free Java and JavaScript hosting!
Static Void Games forum  Come say hello!
Similar Threads

heap sort help
By aizen92 in forum Advanced JavaReplies: 5Last Post: 12052011, 04:33 PM 
Heap Sort
By sehudson in forum New To JavaReplies: 8Last Post: 03312011, 03:25 AM 
Question with bubble sort
By Metastar in forum New To JavaReplies: 22Last Post: 09132010, 06:25 AM 
Heap Sort in Java
By Java Tip in forum AlgorithmsReplies: 0Last Post: 04162008, 10:27 PM 
Heap Sort
By kesav2005 in forum Advanced JavaReplies: 1Last Post: 11132007, 12:40 PM
Bookmarks