Courses‎ > ‎APCS - Term 1‎ > ‎Konstantinovich‎ > ‎

2019-04-11 Heaps

posted Apr 10, 2019, 10:55 AM by Konstantinovich Samuel   [ updated Apr 15, 2019, 5:16 AM ]
Goal: a heaping helping of data structures (Heaps)

DO NOW:
We want a constant time operation to get the max value of a set of numbers. 
We also want to be able to add new numbers to this set and remove the max value.
1.  How could we store the numbers to achieve this?
2. If we did it using a data structure we know about:
    a)What would the insertion speed be?
    b)What would the removal speed be?


One possible category of shapes of trees is a complete binary tree.
complete binary tree -  each level of the tree is completely filled with the possible exception of the bottom level which must be filled from left to right.

Example complete binary tree:

In this example:
If you remove L it would still be complete.
If you remove K, that would violate the requirement that the nodes are filled in from left to right. This would not be a complete tree.
You could remove L and K, then the result would be complete.


What is a heap? (forget implementation for now)

Max Heap - A binary tree with two requirements:
-It is a complete binary tree
-For every element: the data it stores is greater than or equal to the data stored in all of its the children. (0,1,or 2 children)

Min Heap (Same except the data must always be less than the children's data)


Why a heap?
-Speed pf getting the max value?
-Possible speed for adding / removing?

THESE NOTES, AND THE DISCUSSION/DRAWINGS are required to write your heap when your heap lab is given!


Heap<Integer> h = new Heap<>()
h.add(20);
h.add(1);
h.add(23);

Gives you the heap:
  23
 /  \
1    20




h.remove(); //returns 23
And changes the heap to:
  20
 /
1


Let us consider the add operation:
Let us say we want to add a new value. you have conflicting constraints:
-One more element means you need to add something to the left side of the 3.
-Depending on the value of the element it may not go there.

With a neighbor, try to come up with a way to:
1. Add the value 200 to this heap.
2. Add the value 20 to the new heap.
3. What is the runtime of this algorithm?


Now that we have a way to add, consider removing. We only care to remove the largest value!
How would you remove the 200?
With a neighbor, answer the following:
1. What position ultimately must have no value?
2. What would a valid heap look like afterwards?
3. How would you then remove the next largest?
4. What is the runtime of this algorithm?


Implementation:
We need a fast way to access the bottom right most node. How can we implement a way to store this tree?
Can you quickly find the children/parent and the bottom right node this way?


Comments