Results 1 to 9 of 9
Thread: Big Oh Notation and Heaps
 01172008, 12:10 AM #1
Big Oh Notation and Heaps
Hey guys. I have a midterm next friday, and my teacher is giving me an exam from the AP Computer Science AB test. I asked her what would be on it, and i am comfortable with most of the topics (like Stacks, Queues, TreeSets, BinarySearchTrees, etc.), but I have been having trouble with a few topics.
Big Oh Notation. I understand what the point of it is, but i have no idea how to figure it out. For example, if the test gives me an algorithm and i have to figure out the Big Oh Notation, i have no idea how to do this.
Heaps. I understand what they are and why they are used, but i can't seem to understand their Tree representation.
Any help would be greatly appreciated. I am currently reading my textbook trying to understand each topic, but i'm not comprehending it =[
 01172008, 01:07 AM #2
gibson, best of luck on your exam, I'm sure you'll do fine  you display an above average level of intellect on our forums, even though you say you're still somewhat new to the game.
Big O notation is one of the things that I've never enjoyed. I imagine, even in an AP beginning CS course, the emphasis will not be so heavy on big O. This is left for higher level courses such as Analysis of Algorithms. If you have difficulty with your textbook, check over this. Not to repeat what was in the Wiki, but in my experience, that is such the case  that big O represents the running time of the program in relation to the input. You might want to look at it in this way, simply replacing n with a value and seeing what you come up  can it be explained...etc. O(n) where let's say n = 25, that expression O(25) is linear, but when you say O(log 25) = 1.3979, here we've used O(log n) to say the particular algorithm in question is faster than O(n). I don't fully understand it either, so I shouldn't be the authority on this. Maybe others will chime in.
I thought you meant heap, as in the system heap where objects are stored. Heap data structures simply have the rule that the root node is greater than its children. Pretty basic tree data structure here... what about the representation that you're having trouble with could you elaborate on?
CaptVote for the new slogan to our beloved Java Forums! (closes on September 4, 2008)
Want to voice your opinion on your IDE/Editor of choice? Vote now!
Got a little Capt'n in you? (drink responsibly)
 01172008, 01:32 AM #3
Thanks alot man! That really boosts my confidence coming from you!!
As for the Big O:
My teacher said that there are questions on the test where it will give a sorter (such as MergeSort, QuickSort, etc.) and i will have to identify it and determine the big O notation. She said for these, i should just memorize the Big Oh. So, i'm hoping my memorization will be enough. When she gave me review questions, there were questions that asked for the Big O of the addLast method of a class they implemented. I'll try to figure out how this works.
Heaps:
I got a question in my book(I would post the exact question if i had my book on me) that said it inserts 8 Integers into a heap. And then it says, which of the following is an accurate representation of the minheap. And there are 4 choices, and, as i understand, the root nodes of minheaps are the smallest (so i was able to eliminate 2 choices) but the other two were very similar, except that the order was different. But now you said that the root node is greater than its children, so i will see if this solves my problem.
By the way, if you're wondering why i don't ask this stuff to my teacher, it's because, its an AP Computer Science A class, and everyone in my class is learning loops and booleans, so she has no time to teach me, so i learn on my own. Every so often i ask her questions but i'm never fully satisfied. Like i asked her about Big O but she gave me general explanations, couldn't really explain to me how it is obtained. So this is why i come to my friends at JavaForums!
 01172008, 01:37 AM #4Vote for the new slogan to our beloved Java Forums! (closes on September 4, 2008)
Want to voice your opinion on your IDE/Editor of choice? Vote now!
Got a little Capt'n in you? (drink responsibly)
 01172008, 01:42 AM #5
 01252008, 12:26 AM #6
My test is tomorrow morning. Here is that question i was having trouble with.
Suppose that Integers 9, 5, 3, 7, 1 are added, in the order given, to an initially empty queue, q, and that Integers 2, 4, 6, and 8 are added, in the order given, to an initially empty stack, s. Also suppose that hp is an initially empty minheap and that the minhip method addToHeap adds an element to the minheap using the standard algorithm for inserting into a heap thus maintaining the minheap properties after each insertion into the heap. After the following code is executed,
Java Code:while(!q.isEmpty()) { hp.addToHeap(q.dequeue()); } while(!s.isEmpty()) { hp.addToHeap(s.pop()); }
A. 1
/ \
2 3
/ \ / \
6 9 5 4
/ \
7 8
B. 1
/ \
2 5
/ \ / \
3 7 8 6
/ \
9 4
C. 1
/ \
2 3
/ \ / \
4 7 8 6
/ \
9 5
D. 9
/ \
7 4
/ \ / \
8 1 2 3
/ \
5 6
E. 9
/ \
8 7
/ \ / \
6 5 4 3
/ \
2 1

There's the question. Now, as far as i know, the root of the minheap is going to be the smallest number, so 1. So i've ruled out D and E. But to be honest, I don't know whether it's A, B, or C. I'm going to say B.
Someone please help me out, tonight, because my test is tomorrow and there are going to be Heap questions!Last edited by gibsonrocker800; 01252008 at 12:30 AM.
 01252008, 03:01 AM #7
gibson, might you be able to reedit this post and put the tree representations in quotes or code tags  to show their true representation.. ? I hate to be a pest, but I can't tell which children belong to which parent because everything appears to be left aligned  and I'm referring mostly to the last row in each choice.. which I can't be 100% sure if it's leftaligned.. . bah, sorry to have to ask. or could you just confirm the last row belongs to the previous row's left most parent..?
Vote for the new slogan to our beloved Java Forums! (closes on September 4, 2008)
Want to voice your opinion on your IDE/Editor of choice? Vote now!
Got a little Capt'n in you? (drink responsibly)
 01252008, 03:27 AM #8
gibson.. also. After reviewing your specs.. I agree, for the time being, that the resulting tree will have a root key of 1  because this is one of the properties of a minheap, as discussed previously. But also note, that for a queue we know that it's a FIFO structure... so we can assume what will be added to the hp minheap when you call addToHeap, in the same respect we know that a stack employs the LIFO structure.. so we can assume what will be that popped off and added to the hp, I'm sure you know these properties... so now it's just a matter of mentally working through it.
EDIT:
Knowing the properties just mentiond, your queue becomes: 9, 5, 3, 7, 1 << which is reversed, 1 7 3 5 9 where 9 is FIFO. ie:
9
5 9
3 5 9
7 3 5 9
1 7 3 5 9
And with the stack, a slightly different happening: 2 4 6 8 where 8 is LIFO. ie:
2
2 4
2 4 6
2 4 6 8
Keep in mind that for minheaps  the child and parent are compared and swapped if the child is less than the parent.
Now based on the code you provided above, we know that the queue is emptied/added first. Which would go something like this:
9
9
/
5 gets swapped:
5
/
9
Next is 3:
5
/\
9 3 , 3 and 5 are swapped
3
/\
9 5 , next is 7:
3
/\
9 5
/
7 , 9 and 7 are swapped:
3
/\
7 5
/
9 and last is 1 and it gets swapped/compared twice!
3
/\
7 5
/\
9 1 becomes:
3
/\
1 5
/\
9 7 and then becomes:
1
/\
3 5
/\
9 7
I believe it's more evident now how the stack will be emptied/added. I also wish there was a better way to display trees in a forum.... anyways, my resulting answer is the same as yours: B. :) Just for kicks I'm going to run through it, so what's next, 8 !
1
/\
3 5
/\ /
9 7 8 looks fine here, so 6 is next:
1
/\
3 5
/\ /\
9 7 8 6 looks good here too... next is 4:
1
/\
3 5
/\ /\
9 7 8 6
/
4 , 4 gets swapped for 9:
1
/\
3 5
/\ /\
4 7 8 6
/
9 and lastly we have 2, which gets swapped compared/swapped twice:
1
/\
3 5
/\ /\
4 7 8 6
/\
9 2 becomes:
1
/\
3 5
/\ /\
2 7 8 6
/\
9 4 finally becomes:
1
/\
2 5
/\ /\
3 7 8 6
/\
9 4
Thus, B :) heh.. that was fun. ;)Last edited by CaptainMorgan; 01252008 at 04:13 AM.
Vote for the new slogan to our beloved Java Forums! (closes on September 4, 2008)
Want to voice your opinion on your IDE/Editor of choice? Vote now!
Got a little Capt'n in you? (drink responsibly)
 01252008, 10:06 PM #9
Ahh thanks for the help CaptainMorgan. Unfortunately i got a question like this on my test today, I think i might have gotten it right. The test was kinda difficult. The 40 multiple choice questions were okay, i got most of em right. As for the freeresponse. Those were really hard. I did alright on them but not as great as i thought i would. See my problem is that i can't understand what the AP questions ask. And of course they have to set up a class structure for you. I would much rather them to tell me to write a program that does something, and thats it. I like setting up my own structures.
One of the questions was an implementation of a binary search tree. I had to write the peekMin method. basically what i did was,
Java Code://Make a new node that is the same as the root since we are //going to change it. TreeNode newNode = new TreeNode(root, root.getValue()); while(newNode.getLeft() != null) { //I can't remember exactly what i wrote //Something along the lines of continually going to the left //Then, when we reach the bottom node (since the bottom leftmost // node is the smallest which is what we are looking for, return this node) }
Similar Threads

Demonstration of heaps
By Java Tip in forum java.langReplies: 0Last Post: 04142008, 08:50 PM
Bookmarks