Another go at Fibonacci heaps today. We started with the invariants of a Binomial heap as a base to get us started on the invariants of a Fibonacci heap.
We discussed cuts in a Fibonacci heap, and the maximum number of nodes we could cut from a tree so that we don’t have to meld. This is important because we want exponential growth in the trees and we want to keep the rank of each root the same because otherwise we wouldn’t have at most one tree of every rank.
Shout out to Marla for providing us with colored chalk and an exam problem.
We have two new homework assignments for the next couple weeks and I’ll make separate posts for them.
Today we started with Dijkstra’s Algorithm for Single Source Shortest Paths. The reason being that it uses a heap structure to organize nodes that have some minimum distance from the source vertex. The difference is that we need to update (decrement) the value of a vertex in the heap. This is where Fibonacci heaps, which support everything that Binomial heaps do, with the addition of deleting an arbitrary vertex and decrementing the value of an arbitrary vertex.
delete(h, i): O(lg n) (worst case & amortized)
decrement(h, i, D): O(lg n) (worst case) O(1) (amortized)
We didn’t actually cover the structure of Fibonacci heaps, just how we need to modify Binomial heaps to get the bounds we want.
Hopefully, we’ll finish Fibonacci heaps on Wednesday. Don’t forget HW2 is due next lecture as well.
The midterm will be Wednesday, February 22, 2012.
We covered the amortized bounds for the Binomial Heap today. Most of the class was spent talking about amortized analysis and how we can apply it to the insert operation. At the end, we discussed the fact that either the insert or the delete can be chosen to have amortized constant time, but not both. The choice is arbitrary, depending on your application.
Near the end, we also thought about whether the meld operation took amortized constant time, because every tree has been paid for, but one student noted that the NILs do not have a dollar allocated to them, so meld must be O(log n).
Don’t forget to work on the next homework over the weekend.
Today’s topic was Binomial Heaps. We discussed the homework for next week (I’ll make a separate post for it) and covered a bit on Binary Heaps first.
We looked at makeheap, heapify, insert, delete, findmin, and meld operations and discussed their runtime. The meld operation inspired us to move to Binomial Heaps where we can merge two Binomial heaps quickly.
We talked about bounds for these operations for Binomial Heaps as well but we didn’t prove any of them.
Next time, we will finish up these operations and hopefully move on to Fibonacci Heaps.
You can read more about today’s topic in Kozen Ch. 8.
Today’s lecture was about 3SUM as well as the two easier problems (Set Intersection and Search in a Doubly Sorted Array). We discussed ideas for finding good bounds for 3SUM. We talked a bit about Binomial Heaps at the beginning.
*Remember the HW is due Wednesday.
Also, there’s a new homework assignment for next week:
Construct a min-heap in O(n) time.
We’ll start with Binomial Heaps on Wednesday so try to review the lecture in Kozen before the next class.
Good luck guys!