Priority Queue using a min-heap (extra credit)

There were several methods that were discussed to represent a priority queue as a min-heap.  The primary problem was finding an efficient method for finding the position of the element in the tree to hold the new node when a new node is pushed - namely finding its parent to add it to.  That's one of your two problems.  The other is to print out the tree, as a tree (sort of). So...

1. Create the program pqueue_heap.py that will read an input file and write an output file just like pcheck.py program. 

2.In the program file, just underneath the #! /usr/bin/python or #! /usr/bin/python3 line, write a description of how your algorithm works, and in particular, what the Node class's parameters mean -- you'll probably have lots of pointers to other nodes and other stuff, so explain what they do.  You can put all of description into a triple-quoted section.

3. Here are the methods you'll need to implement

PriorityQueue method Example Meaning
push push,2,6,45 pushes one or more (comparable) values into the queue
pop  pop returns and removes the min value, rebalances the heap
peek peek returns the min value, no change to heap
tolist tolist returns a list of popped values until the queue is empty
toheap toheap returns a list of strings, showing the structure of the heap (see below), leaves heap intact

4. There's a small ambiguity in the heap structure that I'd like to resolve.  When a value is "bubbling-down", that value has 3 choices:

a) if all of the value's childen are less than or equal to it, then it has found its natural home, and bubbling ceases, and the heap is now balanced

b) if its children are not equal to each other, and at least one of them is smaller than the value, then the value and its smaller child will swap positions, and bubbling will continue

c) (here's the ambiguity and its resolution): if both the value's children are smaller than the value and happen to be equal to each other, then we have a choice as to which child to swap the value with.  Resolution: swap with the left child, and then continue bubbling-down.

4. Here are the commands you'll get in the input file, just like in the pcheck.py homework, as comma-separated values in separate lines.  Assume that the type of data you'll get, to push into your queue, will be strings.  In the example below, they're capital letters, but they could be strings of any length consisting of alphanumeric characters.

 Let's see these commands in action.  Below, the commands in the input file are preceded with "in: " and the resultant lines output are preceded with "out: ".  The "push" command does not produce results in the output file.  The "toheap" command displays the current layers of the heap, from top layer to bottom layer as separate comma-separated lines -- each line outputs the values for that layer, left to right.  Your program should produce the output lines below given the input lines...

in: push,P,B
in: peek
out: B
in: pop
out: B
in: peek
out: P
in: push,B,R
in: toheap
out: B
out: P,R
in: push,O,O,K,S
in: toheap
out: B
out: O,K
out: P,O,R,S
in: pop
out: B
in: pop
out: K
in: toheap
out: O
out: O,R
out: P,S
in: tolist
out: O,O,P,R,S