Solved

Java heap sorting questions

Posted on 2010-11-27
3
487 Views
Last Modified: 2012-05-10
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?


Website: http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/heap/heapen.htm

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

Open in new window

0
Comment
Question by:prog458
  • 2
3 Comments
 
LVL 37

Expert Comment

by:TommySzalapski
ID: 34224072
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.)

Now just multiply those two numbers together.
0
 

Author Comment

by:prog458
ID: 34228020
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.
0
 
LVL 37

Accepted Solution

by:
TommySzalapski earned 500 total points
ID: 34228044
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

Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
MySqlDump not dumping triggers 1 43
null output 3 35
JAVA API design with micro service cloud in mind 1 42
java example issue 3 20
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…
When there is a disconnect between the intentions of their creator and the recipient, when algorithms go awry, they can have disastrous consequences.
Viewers learn about the scanner class in this video and are introduced to receiving user input for their programs. Additionally, objects, conditional statements, and loops are used to help reinforce the concepts. Introduce Scanner class: Importing…
This video teaches viewers about errors in exception handling.

809 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question