You are being recorded and transcribed.
Approximate overview
Do I really have 10,000 tokens?
Yes, unless you missed class on Friday. In that case, you have only 9,999.
Academic/Scholarly
Cultural
Peer
Wellness
Misc
When will my MPs be graded?
I don’t know. Stay tuned.
Why are you keeping track of a position in JSON.java?
So that your error message can say “Error at position 1432: Unexpected close brace.”
Do we have to do that?
No.
How should I store “\n”?
As a string.
With one character. A newline. (Decimal 10.)
Which means you’ll have to do some conversion when you print it out.
Sorry.
Should we implement remove in our hash tables?
Only if you’d like a sense of accomplishment. It will not affect your grade on the assignment.
Do we have to deal with mulitple JSON objects?
Nope. Just one.
Can we use magic numbers, like 97 and 49?
No.
(int) 'a'is much better than 97.
0is better than 49.
When should JSONstring.equals(X) return true?
When X is a JSONstring and it’s the same string.
Should a real and an integer be equal?
Nope.
TPS!
Philosophy: A linear collection in which we use “highest priority” as
the policy for get or peek.
Use cases: Prioritized to-do list.
Methods: get, put, peek, isEmpty, isFull.
Optional methods: Iterator, highest to lowest.
Comparable objects have
a natural way to determine order.Comparator when we create the PQ object.get or peek, traverse the
array until you find the highest priority element. In get we
grab that element and then (either shift everything in the array
or move the last element into that space). For put, we add
at the end (either crashing when it’s full or expanding the array).
get - O(n)peek - O(n)put - O(1) if we don’t expand the arrayget or peek:
Look at the last element.
get - O(1)peek - O(1)put - O(n)get - O(1)peek - O(1)put - O(n)Sorting with priority queues: PQSort.
n puts.n gets.Can we do better? Yes.
Using binary trees may help.
The heap data structure is not the same thing as heap memory. Computer scientists suck at terminology.
Heaps are Binary trees with some special properties
peekReturn the root. O(1).
putIn order to put, we need to maintain/restore two properties.
Which will be harder to implement?
When we put a value, we add it to the end of the last level (or start a new level if the last level is full). That maintains the “nearly complete” propery.
Once you’ve done that, we need to “heap up” to restore the heap property: As long as a node is higher priority than it’s parent, swap with the parent.
put takes O(log2n) because the height of a nearly-complete tree
is O(log2n). (Alternately, a tree of height k has approximately 2^k
odes.)
Node: O(logn) and O(log2n) are the same because logn = clog2n and Sam is too lazy to figure out that constant.
getWe remove the highest priority node at the root and then we have two properties to restore: “Nearly complete” and “Heap Property”.
Take the rightmost value on the last level and put it at the root
Repeatedly swap with higher priorty child, provided that child has a higher priority than the value.
This is O(logn)
PQSort with heaps is O(nlogn)!
How do we know when a level is full?
When there are 2^n-1 items in the tree.
Could we perhaps implement something more complicated involving swapping subtrees?
Perhaps. But this is simple. Let’s stick with this for now.
Swap up involves identifying your parent. How do we find the parent?
We build nodes that have a parent link in addition to the two children links. “Ugh”
We can store heaps in arrays, using a breadth-first, left-to-right, preorder numbering of the nodes.
The left child of the node at index i is at index 2*i+1
The right child of the node at index i is at index 2*i+2
The parent of the node at index i is at index ???
(i-1)/2.We save space. We don’t have to worry about left pointers, right pointers, or parent pointers. Yay!
Any binary tree can be stored in this manner. You’ll just have gaps.
Now it’s really easy to find the last node on the last level. We don’t even have to ask our friends in math for a formula.
Done.
+------------------------+--------------+
| heap | sorted |
+------------------------+--------------+
+------------------------+--------------+
|l| heap | sorted |
+------------------------+--------------+
to
+----------------------+-+--------------+
| heap |l| sorted |
+----------------------+-+--------------+
If we do that repeatedly, we end up with a sorted array.
Heap sort:
Selection sort, but much faster.
All that’s left is to turn an unsorted array into a heap.
The obvious strategy.
for (int i = 1; i < n; i++) {
swapUp(i);
}
Another one (coming next class)
Is this better than other ways of sorting?
Merge sort: Requires a helper array. This is better.
Quicksort: Isn’t always O(nlogn); you can choose bad pivots.
In practice?
Things get more complicated.
It’s also unstable.