"""Greedy Algorithms A greedy algorithm always makes the choice that looks the best at the moment. That is, it makes a locally optimal choice in the hope that this choice will lead to a globally optimal solution. For some optimization problems, the greedy algorithm does not yield optimal solutions but for many problems, it does. """ # def greedy_cpu_scheduling(s, f): # n = len(s) # A = [0] # j = 0 # for i in xrange(1, n-1): # if s[i] >= f[j]: # A.append(i) # j = i # return A ###################################################################### # Huffman Example class HuffmanNode: def get_frequency(self): return 0 def __str__(self): return str(self.get_frequency()) def __cmp__(self, other): a = self.get_frequency() b = other.get_frequency() if a < b: return -1 elif a > b: return +1 else: return 0 class HuffmanLeafNode(HuffmanNode): def __init__(self, character, frequency): self.character = character self.frequency = frequency def get_frequency(self): return self.frequency def get_character(self): return self.character def set_binary(self, binary='0'): self.binary = binary def print_tree(self): print "CHARACTER: %s, FREQUENCY: %2d, BINARY: %s"%(self.character, self.frequency, self.binary) def get_total_bits(self): return len(self.binary) * self.frequency class HuffmanBranchNode(HuffmanNode): def __init__(self, left, right): self.left = left self.right = right self.frequency = left.get_frequency() + right.get_frequency() def get_frequency(self): return self.frequency def get_left(self): return self.left def get_right(self): return self.right def set_binary(self, binary=''): self.left.set_binary(binary+'0') self.right.set_binary(binary+'1') def print_tree(self): self.left.print_tree() self.right.print_tree() def get_total_bits(self): return self.left.get_total_bits() + self.right.get_total_bits() def huffman(C): """Return a Huffman tree from a list of HuffmanLeafNodes.""" import binary_heap Q = binary_heap.BinaryHeap(binary_heap.min_priority) n = len(C) for c in C: Q.insert(c) for i in xrange(n-1): if DEBUG: print "Items in queue:", __list_freq(Q.get_items()) x = Q.extract() if DEBUG: print "Items in queue:", __list_freq(Q.get_items()) y = Q.extract() z = HuffmanBranchNode(x, y) if DEBUG: print "Merged %d and %d into %d" %(x.get_frequency(), y.get_frequency(), z.get_frequency()) Q.insert(z) root = Q.extract() assert(Q.is_empty()) return root def __list_freq(C): for c in C: print c.get_frequency(), print ###################################################################### # TEST DEBUG=False #DEBUG=True def test(): data = {'a':45, 'b':13, 'c':12, 'd':16, 'e':9, 'f':5} C = [] for character in data.keys(): C.append(HuffmanLeafNode(character, data[character])) print "Items in C:", __list_freq(C) R = huffman(C) R.set_binary() R.print_tree() print "Total bits required:", R.get_total_bits() if __name__ == '__main__': test()