<p>How well do we need to know heapsorts? I know the basic algorithm and Big O runtimes, but how important is the code?</p>
<p>Basically my teacher has informed us that you have to be able to recognize each sort so that if there is a code question you can easily answer the questions without having to work it all out. So know how it works, and you should be fine.</p>
<p>the basic algorithim for heapsort is really easy: just copy everything over into a heap (probably a PriorityQueue), then copy everything back. the only tricky part of the code is if they ask you to write the add and remove methods of a heap.
the general formula for adding to a heap is: (assuming this is a MIN heap implemented as a primitive array)</p>
<p>public void addToHeap(int a, int x, int sizeOfHeap)
{
a[sizeOfHeap] = x;
bumpUp(int a, sizeOfHeap);
sizeOfHeap++;
}
private void(int a, int y)
{
if(a[y] < a[y/2])
{
swap(a, y, y/2);
bumpUp(a, y/2);
}</p>
<p>removing from a heap is a bit trickier:</p>
<p>public int removeFromHeap(int a, int sizeOfHeap)
{
int retvalue = a[1];
a[1] = a[sizeOfHeap];
a[sizeOfHeap] = 0; // 0 is the “null” value of int
sizeOfHeap–;
bumpDown(a, 1, sizeOfHeap)
return retvalue;
}
private void bumpDown(int a, int x, int sizeOfHeap)
{
if( 2 * x > sizeOfHeap)
{
return;
}
if(a[2 * x] > a[2 * x + 1])
{
swap(a, 2 * x, 2 * x + 1)
}
if(a > a[2 * x] && a > a[2*x + 1])
{
swap(a, x, 2 * x);
bumpDown(a, 2 * x, sizeOfHeap);
}
if(a > [2 * x + 1])
{
swap(a, x, x * 2 + 1);
bumpDown(a, 2 * x + 1, sizeOfHeap);
}
}</p>
<p>i think that’s about it as far as heap sorting goes. gl!</p>