Week 13 Day 2 - Heaps
2The first half of class we talked about some new things in the C++ language that we haven't covered before, enums and enum classes, as well as giving a preview for a new topic that we'll be hitting later - inheritance. Enums are ways of making lots of constant integers all at the same time that don't have the same value (useful for like menu options and the like, and tie in nicely with switch statements), enum classes create a new type that have limited options for the values. If you want a char (like in my example) that can only have one of three values, then you can make an enum class like I did, and the language will enforce that rule for you.
Inheritance is a big topic, what I showed today was a small part of it, the notion of creating an interface using what's called an "abstract class" that doesn't do anything but define a set of functions that all of its subclasses will have, and then subclassing it to implement those functions in different ways. If you have a pointer (of the type of the abstract class) you can point it at either of the subclasses by calling new on the subclass. (Even better would be to use a smart pointer, but I haven't taught them yet.) Thus you can have the same variable getting insert, search, etc., called on it, but switch out the implementation from one type of hash table to another. Neat stuff.
Make sure you start early on the hash table assignment - it's not a lot of coding, but the benchmarking can take a while, and you don't want to start benchmarking on the day before it's due.
Next, we started talking about a new data structure, the heap. A heap is a binary tree that is not a binary search tree. Whereas binary search trees have the rule, "All elements to the left are smaller", max-heaps have the rule "Everyone below me is smaller", and min-heaps have the rule "Everyone below me is bigger". This makes it really easy to find the max element (for a max-heap) or the min element (for a min-heap), however finding any other element in the heap is O(N) since it's not sorted beyond this in any meaningful fashion. It does have the ability to insert into the data structure in O(logN) time and pop off the top in O(logN) time, while maintaining its class invariant.
This allows us to write an optimal (in terms of Big-O) sorting algorithm by simply pushing a bunch of elements into a heap and popping them back out. N inserts at logN per insert = NlogN to insert all the elements. N pops at logN work per pop = NlogN work to delete all the elements. So the overall running time is O(NlogN + NlogN) or O(2NlogN) or O(NlogN) time, which is optimal for sorting random data.
Heaps are also nice in that they're always dense and balanced, and so can be held in a vector instead of needing to mess around with pointers (which can eat up a lot of memory in overhead).