Python 3.x HuffmanHeap Question I keep getting someone spamming me the wrong answer with no explaination, which I have no idea how it works and I can't learn from that. I know that they're getting it from a website with no context as to help me, because that's not what I'm trying to do. So if you're that anonnymous poster who keeps copying and pasting from that website about huffman heaps, that's incorrect and please stop doing that.

What I personally understand the question to be is to use classes to create a Huffmanheap. A Huffman Heap is a queue to store HuffmanTree objects. The code for the HuffmanTree objects is already there, so I do not need to work on that.The word "heap" implies that the dequeue operation will always remove and return the HuffmanTree object with the lowest frequency.

I did start the question, the problem is I don't know where to go or how to finish it or even if I'm on the right track.

Code for HuffmanHeap:

class HuffmanHeap(object): def __init__(self, leafs): """  Purpose:  Creates a new HuffmanHeap object.  Pre-conditions:  leafs: a list of HuffmanTree leaf nodes.  Post-conditions:  The heap is created and initialized.  Return:  None  """  # self.leafs = leafs --unsure if this is correct or if I'm on the right track pass

 def enqueue(self, tree): """  Purpose:  Adds the tree to the Heap.  This is an O(1) operation.  Pre-conditions:  tree is a HuffmanTree object  Post-conditions:  the heap increases in size by 1  Return:  None  """  return None def dequeue(self): """  Purpose:  Return the smallest value in the queue.  This is an O(1) operation.  Pre-conditions:  None  Post-conditions:  The heap decreases in size by 1  Return:  A HuffmanTree object, with the lowest frequency  """  return None def __len__(self): """  Purpose:  Return the number of data values stored in the heap.  This method allows Python scripts to call len(hh)  if hh is a HuffmanHeap object.  Pre-conditions:  None  Post-conditions:  None  Return:  The number of values stored in the heap  """  return 0 def display(self): """  Purpose:  Display the data for debugging.  Pre-conditions:  None  Post-conditions:  None  Return:  None  """  print('Add code to HuffmanHeap.display() to help you debug.') 

I am supposed to complete the four methods:

Now here is the Huffman Tree data structure, that doesn't need to fixed as it's correct I just figure you need everything I have for help:

class HuffmanTree(object): def __init__(self, freq=0, char=None, left=None, right=None): """  Purpose:  Initializes the HuffmanTree object.  To create a leaf node  aleaf = HuffmanTree(freq=10, char='A')  bleaf = HuffmanTree(freq=15, char='E')  To create an internal node:  node = HuffmanTree(left=aleaf,right=bleaf)   Pre-conditions:  :param freq: a positive integer  :param char: a character  :param left: another Huffman Tree  :param right: another HuffmanTree  """  self.__char = char self.left = left self.right = right if left is None and right is None: # leaf node: assign the frequency as given self.__freq = freq else: assert left is not None and right is not None, _INIT_ASSERT_MESSAGE_NONLEAF # non-leaf node: calculate the frequency from the given subtrees self.__freq = left.__freq + right.__freq def is_leaf(self): """  Purpose:  Check if the node is a leaf.  Simplifies some of the other methods with an abstraction.  Return:  True if the node is a leaf node  """  return self.left is None and self.right is None def get_freq(self): """  Purpose:  Return the frequency data stored in the node.  Return:  :return: the frequency  """  return self.__freq def get_char(self): """  Purpose:  Return the character stored at a leaf node.  Return:  :return: the character at a leaf node  """  assert self.is_leaf(), _GETCH_ASSERT_MESSAGE_NONLEAF return self.__char def display(self, level=0): """  Purpose:  For debugging, display the tree.  The structure of the tree is represented by indentation  No other real purpose.  Preconditions:  :param level: indentation amount for subtrees.  Return  :return: None  """  if self.is_leaf(): print(' '*level+'Leaf:', self.__char, self.__freq) else: print(' '*level+'Node:', self.__freq, 'Children:') self.left.display(level+1) self.right.display(level+1) def build_codec(self): """  Purpose:  Build a dictionary of char-code pairs from the Huffman tree.  Return:  :return: a dictionary with character as key, code as value  """  codes = {} def encoder(tree, code): if tree.is_leaf(): codes[tree.get_char()] = code else: encoder(tree.left, code+'0') encoder(tree.right, code+'1') if self.is_leaf(): codes[self.__char] = '0' else: encoder(self,'') return codes def __lt__(self, other): return self.__freq  
Here is a picture of a huffman tree:
 
 
 
 
And here is the Encoder that once again doesn't need to be fixed but just an idea of how huffmanheap should integrate with the code:
 
import sys as sys import HuffmanTree as HT import HuffmanHeap as HH DEFAULT_OUTPUT_FILE = 'encoded.txt' def main(): """  Purpose:  Application to read and encode a file using Huffman codes.  Usage: python3 Encoder.py   Sends output to DEFAULT_OUTPUT_FILE  Return:  :return: None  """  if len(sys.argv) != 2: print('Usage: python3', sys.argv[0], '') print('-- sends output to', DEFAULT_OUTPUT_FILE, '-- ') return fname = sys.argv[1] lines = read_file(fname) freqs = count_characters(lines) codec = build_codec(freqs) coded = encode(lines, codec) write_file(DEFAULT_OUTPUT_FILE, coded) def read_file(fname): """  Purpose:  Read a file and return contents in a list of strings.  Preconditions:  :param fname: the name of a text file  Return:  :return: a list of strings, one string for each line  """  tfile = open(fname) lines = [l.rstrip() for l in tfile] tfile.close() return lines def write_file(fname, lines): """  Purpose:  Write the data in lines to the named file.  Warning: this will over-write any data in the named file!  Preconditions:  :param fname: the name of a text file  :param lines: a list of strings  Post-condition:  The named file is created or over-written.  Return:  :return: None  """  tfile = open(fname, 'w') for line in lines: tfile.write(line + ' ') tfile.close() def count_characters(contents): """  Purpose:  Count the characters in the contents.  Pre-conditions:  :param contents: a list of strings.  Return:  :return: a list of (character,frequency) tuples  """  freqs = dict() for line in contents: for char in line: if char in freqs: freqs[char] += 1 else: freqs[char] = 1 return list(freqs.items()) def build_codec(freq_list): """  Purpose:  Build a codec from the frequency list.  Pre-conditions:  :param freq_list: A list of (char,frequency) tuples.  Return:  :return: a dictionary mapping characters to codes  """  freq_list.sort(key=lambda p: p[1]) hq = HH.HuffmanHeap([HT.HuffmanTree(freq=f,char=c) \ for c,f in freq_list]) while len(hq) > 1: t1 = hq.dequeue() t2 = hq.dequeue() hq.enqueue(HT.HuffmanTree(left=t1, right=t2)) survivor = hq.dequeue() return survivor.build_codec() def encode(strings, codec): """  Purpose:  Use the codec to create the data to be sent to the output file.  Pre-conditions:  :param strings: A list of strings to encode.  :param codec: A dictionary containing character-code pairs  Return:  :return: a list of strings including:  the number of codes the number of coded lines,  the codes  the coded lines  """  output = [] output.append(str(len(codec)) + ' ' + str(len(strings))) for char in codec: output.append(codec[char] + ':' + "'" + char + "'") for s in strings: encoded = [] for char in s: encoded.append(codec[char]) output.append(''.join(encoded)) return output if __name__ == '__main__': main() 
 
 
 
 
  . .init..(self, leafs): Creates a new HuffmanHeap object. enqueue (self, tree): Adds the given HuffmanTree to the heap. dequeue (self): Removes and returns the smallest HuffmanTree in the heap. ...len_.(self): Returns the number of HuffmanTrees in the heap. Defining this method allows pro- grammers to call len ) on HuffmanHeap objects In lecture we saw that we could implement these operations so that they all have O(n) worst case time complexity, where n is the number of HuffmanTree objects in the HuffmanHeap. However, we also de- scribed in lecture how these operations could be implemented so that they all have worst case time com- plexity of O(1). Hint: use 2 lists. The HuffmanHeap class is incomplete. Your job is to complete the 4 methods described above, so that the Encoder.py program correctly encodes text files.  . .init..(self, leafs): Creates a new HuffmanHeap object. enqueue (self, tree): Adds the given HuffmanTree to the heap. dequeue (self): Removes and returns the smallest HuffmanTree in the heap. ...len_.(self): Returns the number of HuffmanTrees in the heap. Defining this method allows pro- grammers to call len ) on HuffmanHeap objects In lecture we saw that we could implement these operations so that they all have O(n) worst case time complexity, where n is the number of HuffmanTree objects in the HuffmanHeap. However, we also de- scribed in lecture how these operations could be implemented so that they all have worst case time com- plexity of O(1). Hint: use 2 lists. The HuffmanHeap class is incomplete. Your job is to complete the 4 methods described above, so that the Encoder.py program correctly encodes text files