Sign up to receive Decoded, a new monthly digest with product updates, feature release info, continuing education opportunities, and more.
public class HeapSorter
{
private static int[] a;
private static int n;
public static void sort(int[] a0)
{
a=a0;
n=a.length;
heapsort();
}
private static void heapsort()
{
buildheap();
while (n>1)
{
n--;
exchange (0, n);
downheap (0);
}
}
private static void buildheap()
{
for (int v=n/2-1; v>=0; v--)
downheap (v);
}
private static void downheap(int v)
{
int w=2*v+1; // first descendant of v
while (w<n)
{
if (w+1<n) // is there a second descendant?
if (a[w+1]>a[w]) w++;
// w is the descendant of v with maximum label
if (a[v]>=a[w]) return; // v has heap property
// otherwise
exchange(v, w); // exchange labels of v and w
v=w; // continue
w=2*v+1;
}
}
private static void exchange(int i, int j)
{
int t=a[i];
a[i]=a[j];
a[j]=t;
}
} // end class HeapSorter
Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.
Have a better answer? Share it in a comment.
I don't see any destruction code, but the entire heap is stored in a single array. So how many steps would it take to 'destroy' that?
Your questions 1 and 2 appear to be the same. This is how you would count the construction steps. Look at how many times the for loop in buildheap runs. So for each of those you do downheap. What is the highest amount of steps that downheap could take? (Hint: the heap is a binary heap so the maximum height is known. You should know what it is too.)
Now just multiply those two numbers together.