Tip:
Highlight text to annotate it
X
Now speaking precisely.
A heap isn't actually any particular data structure with some particular running time.
It's actually kind of an abstract data type. It's a data type that supports three different operations.
We have some kind of data and we can add a new number to say the set.
We can also ask, of all the numbers that are in the set what's the smallest that we've got?
And we can say, if you don't mind please remove the smallest from the structure that we have
doing whatever updates are necessary so that the rest of the operations can be fulfilled.
And we can implement these operations using ideas that we've already got.
So things like we can insert into a structure, we can ask what's the smallest element in the structure,
and we can remove the structure from it.
Let's use this as an excuse to do a little review.
Here's two natural ways of implementing the heap operations of inserting
and finding and removing the minimum from the structure.
We can do it with an ordered list or we can do it with an unordered list.
And there's tradeoffs to doing it this way.
What I'd like you to do is, for how long does it take to do an insert into an ordered list of logn.
Is that constant time, log time, or linear time? Same thing for an unordered list.
How long does it take to stick a new item into the list?
And finally, now that you've done that, we've inserted a bunch of elements
into the list and they're in there now and we want to ask the question,
how long does it take to find and remove the minimum from an ordered list?
Is it constant, log, or linear?
Form an unordered list, to find the minimum value and remove it.
I'd like for each of these rows you should check exactly one of the boxes.