Could anyone please help me to understand this code:
That is java class which sorts array.
Questions:
1) What are the numbers of steps you needed to build the heap, and to destroy the heap?
2) How to get the sum of the construction and destruction steps?

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 trying to actually count the instructions? In that case just make a global variable start it at 0 and increment it in the loop in downheap and nowhere else.
If you want the runtime, you don't

Since this is most likely a school assignment of some kind, we can't just give out answers but I can sure point you to how to solve it.

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.)

Thanks for help i think i am getting there. How can i put those numbers into code. It would be ok with buildheap. How would i do with a downheap?
Theoretically it says h=log(Base2)(N+1)-1 - max hight.The thing is i want to generate that answer from code. Do you have any suggestions.

Are you trying to actually count the instructions? In that case just make a global variable start it at 0 and increment it in the loop in downheap and nowhere else.
If you want the runtime, you don't want or need it in the code. They want the average case runtime which you can see is O(n*lg(n))
The current hight of the heap can be calculated as the number of times the loop in downheap runs.

0

Featured Post

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

The greatest common divisor (gcd) of two positive integers is their largest common divisor. Let's consider two numbers 12 and 20.
The divisors of 12 are 1, 2, 3, 4, 6, 12
The divisors of 20 are 1, 2, 4, 5, 10 20
The highest number among the c…

Introduction
This article is the second of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers the basic installation and configuration of the test automation tools used by…

Viewers will learn about the different types of variables in Java and how to declare them.
Decide the type of variable desired:
Put the keyword corresponding to the type of variable in front of the variable name:
Use the equal sign to assign a v…

Viewers will learn one way to get user input in Java.
Introduce the Scanner object:
Declare the variable that stores the user input:
An example prompting the user for input:
Methods you need to invoke in order to properly get user input: