Differences

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

--- courses:cs211:winter2012:journals:jeanpaul:chapterfour_sectionviii [2012/03/06 05:25] – 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)\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> 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'  \\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> 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. \\
->>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> probabilities. Takes O(1) time. \\
 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Add the new node to the queue Takes O(logn)\\
 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> The remaining node is the tree’s root node.\\