Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2012:journals:jeanpaul:chapterfour_sectionviii [2012/03/06 05:18] – mugabej
+++ courses:cs211:winter2012:journals:jeanpaul:chapterfour_sectionviii [2012/03/06 05:27] (current) – [Implementation and Running Time] mugabej
@@ Line 74: / Line 74: @@
 ==== Implementation and Running Time ====
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Create a leaf node for each symbol, labeled by its frequency, and add to a\\ queue(PQ).Takes O(nlogn)\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> While there is more than one node in the queue: Takes O(n)\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Remove the two nodes of lowest frequency. Takes O(logn)\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Create a new internal node with these two nodes as children and\\ with frequency equal to the sum of the two nodes' probabilities. Takes O(1) time. \\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Add the new node to the queue Takes O(logn)\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> The remaining node is the tree’s root node.\\
+\\
+So overall takes O(nlogn).\\
+\\
+Very intriguing section although its proofs were long. I give it an 8/10.