Heaps and Python (WS) (1/26/15)

Today I worked on the Heaps worksheet. Although I actually haven't written or even seen Python in the past few years, this refreshed my knowledge a bit on it and also allowed me to learn about Heaps a bit more! I finished the worksheet and I got them correct in the end. I learned about the following.

Heap Up - Used when you want to insert a value into a heap. Recursively goes through the current heap to figure out where to put the new value.

Heap Down - Used when you want to remove a value. Recursively goes through the current heap, by rebuilding it without the value.

I also learned about translating a list into a heap. It's fairly simple:

For the left value, you can use 2*i, where i is the index of the value.
For the right value, you can use 2*i+1, where i is the index of the value.

From here, you basically are filling out values from left to right.
For example, if your list is [1, 2, 3, 4, 5, 6, 7], your heap wouldn't be correct. You'd have to use one of the above methods to fix it. In the worksheet example, we recursively used heap_down. From there, it fixed the heap, leaving it to a correct heap. Using the example, our new heap would be [1, 7, 6, 4, 5, 3, 2]. This would be a Min-Heap, and would look like this:

    1

   7      6

  4   5   3  2

The worksheet really helped with a lot of Heap concepts that EIMACS didn't explain to the fullest. I think that it did help me learn a bit more about the basic properties of Heaps and some ways that they can be created and modified.