class Heap(object): """ A max heap, parents have two or less equal or smaller children """ def __init__(self): """ Set the count to 0 and it has no root node """ self.count = 0 self.root = None def heapify(self, iterable): """ loops elements in the iterable and adds them to the heap """ for elem in iterable: self.add_item(elem) def add_item(self, ordinal): """ Adds an ordinal item using priority """ self.count += 1 if self.count == 1: self.root = Node(ordinal) return i = self.count current_node = self.root new_node = Node(ordinal) while i != 1: if current_node.data < new_node.data: current_node.data, new_node.data = new_node.data, current_node.data if i%2 == 0: if current_node.left: current_node = current_node.left else: current_node.left = new_node else: if current_node.right: current_node = current_node.right else: current_node.right = new_node i /= 2 class Node(object): """ Used to traverse the heap """ def __init__(self, ordinal): """ Require data, make the pointers empty (to None) """ self.data = ordinal self.left = None self.right = None
This design of a heap is pretty interesting because it uses the binary representation of
Heap.count
(the number of elements in the heap) to determine where the next node should go. The algorithm for this is pretty straight forward:Increment the `count` by 1 // We're adding a new item `i` is `count` `current node` is `root node` Check 1: if `new node's value` > `current node's value`, then swap(`new node's value`, `current node's value`) Check 2: if binary(`i`) ends in 0, // AKA is even, (i%2 == 0), then `current node` is `current node's left` otherwise `current node` is `current node's right` Check 3: if `current node` is null then `current node` is `new node` otherwise `i` /= 2 and goto Check 1
The end result is a balanced heap! I also added a
__str__
method to the Node class for testing:def __str__(self): return "[%s <- %s -> %s]" % \ (str(self.left) if self.left != None \ else 'END', str(self.data), \ str(self.right) if self.right != None \ else 'END')
No comments:
Post a Comment