<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Lecture 14
Wednesday, October 25th 2017
Last time
Step1:  Example Usage
Step2:  Every collection in Python is iterable.
We have already seen iterators are used to make for loops. They are also used to make other collections
Step3:  Some notes on generators
When next is called on the generator, the function proceeds until the first yield.
The function body is now suspended and the value in the yield is then passed to the calling scope as the outcome of the next.
When next is called again, it gets __next__ called again (implicitly) in the generator, and the next value is yielded.
This continues until we reach the end of the function, the return of which creates a StopIteration in next.
Any Python function that has the yield keyword in its body is a generator function.
Step4:  More notes on generators
Generators yield one item at a time
In this way, they feed the for loop one item at a time
Step5:  Lecture Exercise
Create a Sentence iterator class that uses a generator expression.  You will write the generator expression in the __iter__ special method.  Note that the generator automatically gets __next__.
<ASSISTANT_TASK:>
Python Code:
class SentenceIterator:
    def __init__(self, words): 
        self.words = words 
        self.index = 0
        
    def __next__(self): 
        try:
            word = self.words[self.index] 
        except IndexError:
            raise StopIteration() 
        self.index += 1
        return word 
    def __iter__(self):
        return self
class Sentence: # An iterable
    def __init__(self, text): 
        self.text = text
        self.words = text.split()
        
    def __iter__(self):
        return SentenceIterator(self.words)
    
    def __repr__(self):
        return 'Sentence(%s)' % reprlib.repr(self.text)
Explanation: Lecture 14
Wednesday, October 25th 2017
Last time:
Iterators and Iterables
Trees, Binary trees, and BSTs
This time:
BST Traversal
Generators
Memory layouts
Heaps?
BST Traversal
We've stored our data in a BST
This seemed like a good idea at the time because BSTs have some nice properties
To be able to access/use our data, we need to be able to traverse the tree
Traversal Choices
There are three traversal choices based on an implicit ordering of the tree from left to right:
In-order: Traverse left-subtree, then current root, then right sub tree
Post-order: Traverse left subtree, then traverse left subtree, and then current root
Pre-order: Current root, then traverse left subtree, then traverse right subtree
Traversing a tree means performing some operation
In our examples, the operation will be "displaying the data"
However, an operation could be "deleting files"
Example
Traverse the BST below using in-order, post-order, and pre-order traversals.  Write the resulting sorted data structure (as a list is fine).
Heaps
We listed several types of data structures at the beginning of our data structures unit.
So far, we have discussed lists and trees (in particular binary trees and binary search trees).
Heaps are a type of tree, a little different from binary trees.
Some Motivation
Priority Queues
People may come to your customer service counter in a certain order, but you might want to serve your executive class first! 
In other words, there is an "ordering" on your customers and you want to serve people in the order of the most VIP.
This problem requires us to then sort things by importance and then evaluate things in this sorted order.
A priority queue is a data structure for this, which allows us to do things more efficiently than simple sorting every time a new thing comes in.
Items are inserted at one end and deleted from the other end of a queue (first in, first out [FIFO] buffer).
The basic priority queue is defined to be supporting three primary operations:
1. Insert: insert an item with "key" (e.g. an importance) $k$ into priority queue $Q$.
2. Find Minimum: get the item, or a pointer to the item, whose key value is smaller than any other key in $Q$.
3. Delete Minimum: Remove the item with minimum $k$ from $Q$.
Comments on Implementation of Priorty Queues
One could use an unsorted array and store a pointer to the minimum index; accessing the minimum is an $O(1)$ operation.
* It's cheap to update the pointer when new items are inserted into the array because we update it in $O(1)$ only when the new value is less than the current one.
* Finding a new minimum after deleting the old one requires a scan of the array ($O(n)$ operation) and then resetting the pointer.
One could alternatively implement the priority queue with a balanced binary tree structure.  Then we'll get performance of $O(\log(n))$!
This leads us to heaps.  Heaps are a type of balanced binary tree.
A heap providing access to minimum values is called a min-heap
A heap providing access to maximum values is called a max-heap
Note that you can't have a min-heap and max-heap together
Heapsort
Implementing a priority queue with selection sort takes $O(n^{2})$ operations
Using a heap takes $O(n\log(n))$ operations
Implementing a sorting algorithm using a heap is called heapsort.
Heapsort is an in-place sort and requires no extra memory.
Note that there are many sorting algorithms nowadays.  Python uses Timsort.
Back to Heaps
A heap has two properties:
Shape property
A leaf node at depth $k>0$ can exist only if all the nodes at the previous depth exist. Nodes at any partially filled level are added "from left to right".
Heap property
For a min-heap, each node in the tree contains a key less than or equal to either of its two children (if they exist).
This is also known as the labeling of a "parent node" dominating that of its children. 
For max heaps we use greater-than-or-equal.
Heap Mechanics
The first element in the array is the root key
The next two elements make up the first level of children.  This is done from left to right
Then the next four and so on.
More Details on Heap Mechanics
To construct a heap, insert each new element that comes in at the left-most open spot. 
This maintains the shape property but not the heap property.
Restore the Heap Property by "Bubbling Up"
Look at the parent and if the child "dominates" we swap parent and child. Repeat this process until we bubble up to the root.
Identifying the dominant is now easy because it will be at the top of the tree.
This process is called heapify and must also be done at the first construction of the heap.
Deletion
Removing the dominant key creates a hole at the top (the first position in the array).
Fill this hole with the rightmost position in the array, or the rightmost leaf node.
This destroys the heap property!
So we now bubble this key down until it dominates all its children.
Example
Construct a min-heap for the array $$\left[1, 8, 5, 9, 23, 2, 45, 6, 7, 99, -5\right].$$
Delete $-5$ and update the min-heap.
Iterables/Iterators Again
We have been discussing data structures and simultaneously exploring iterators and iterables.
End of explanation
a = Sentence("Dogs will save the world and cats will eat it.")
for item in a:
    print(item)
print("\n")
it = iter(a) # it is an iterator
while True:
    try:
        nextval = next(it)
        print(nextval)
    except StopIteration:
        del it
        break
Explanation: Example Usage
End of explanation
def gen123():
    print("A")
    yield 1
    print("B")
    yield 2
    print("C")
    yield 3
g = gen123()
print(gen123, "   ", type(gen123), "   ", type(g))
print("A generator is an iterator.")
print("It has {} and {}".format(g.__iter__, g.__next__))
Explanation: Every collection in Python is iterable.
We have already seen iterators are used to make for loops. They are also used to make other collections:
To loop over a file line by line from disk
In the making of list, dict, and set comprehensions
In unpacking tuples
In parameter unpacking in function calls (*args syntax)
An iterator defines both __iter__ and a __next__ (the first one is only required to make sure an iterator is an iterable).
Recap: An iterator retrieves items from a collection. The collection must implement __iter__.
Generators
A generator function looks like a normal function, but yields values instead of returning them. 
The syntax is (unfortunately) the same otherwise (PEP 255 -- Simple Generators).
A generator is a different beast. When the function runs, it creates a generator.
The generator is an iterator and gets an internal implementation of __iter__ and __next__.
End of explanation
print(next(g))
print(next(g))
print(next(g))
print(next(g))
Explanation: Some notes on generators
When next is called on the generator, the function proceeds until the first yield.
The function body is now suspended and the value in the yield is then passed to the calling scope as the outcome of the next.
When next is called again, it gets __next__ called again (implicitly) in the generator, and the next value is yielded.
This continues until we reach the end of the function, the return of which creates a StopIteration in next.
Any Python function that has the yield keyword in its body is a generator function.
End of explanation
for i in gen123():
    print(i, "\n")
Explanation: More notes on generators
Generators yield one item at a time
In this way, they feed the for loop one item at a time
End of explanation
class Sentence:
    def __init__(self,sentence):
        self.sentence=sentence
        self.words=sentence.split()
    def __iter__(self):
        for i in range(len(self.words)):
            yield self.words[i]
    def __repr__(self):
        return 'Sentence(%s)' % reprlib.repr(self.words)
            
        
        
a = Sentence("Dogs will save the world and cats will eat it.")
for item in a:
    print(item)
print("\n")
Explanation: Lecture Exercise
Create a Sentence iterator class that uses a generator expression.  You will write the generator expression in the __iter__ special method.  Note that the generator automatically gets __next__.
End of explanation
<END_TASK>