chess:programming:huffman:example
Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| chess:programming:huffman:example [2021/10/29 13:41] – peter | chess:programming:huffman:example [2021/10/29 13:56] (current) – [Stepping through the code] peter | ||
|---|---|---|---|
| Line 199: | Line 199: | ||
| * It is extended as needed to accommodate the values of internal tree nodes. | * It is extended as needed to accommodate the values of internal tree nodes. | ||
| * **C** is the set of characters represented as leaf tree nodes. | * **C** is the set of characters represented as leaf tree nodes. | ||
| - | * **Q* is a priority queue of tree nodes where we can quickly extract the minimum element; | + | * **Q** is a priority queue of tree nodes where we can quickly extract the minimum element; |
| * this can be done with a heap where the heap property is reversed. | * this can be done with a heap where the heap property is reversed. | ||
| * We build the tree in a bottom up manner, starting with the individual characters and ending up with the root of the tree as the only element of the queue. | * We build the tree in a bottom up manner, starting with the individual characters and ending up with the root of the tree as the only element of the queue. | ||
| Line 212: | Line 212: | ||
| ---- | ---- | ||
| - | ==== Stepping through the code ==== | + | ==== Stepping through the code using the Huffman algorithm |
| - | Let's go through the above example using Huffman' | + | Here are the contents of **Q** after each step through the for loop: |
| - | + | ||
| - | Here are the contents of Q after each step through the for loop: | + | |
| Initially, all nodes are leaf nodes. | Initially, all nodes are leaf nodes. | ||
| Line 235: | Line 233: | ||
| | | ||
| </ | </ | ||
| + | |||
| + | ---- | ||
| Then the next two with least value, Q has 6 elements: | Then the next two with least value, Q has 6 elements: | ||
| Line 244: | Line 244: | ||
| | | ||
| </ | </ | ||
| + | |||
| + | ---- | ||
| Now the two nodes with least values are the two trees we just made, and Q has 5 elements: | Now the two nodes with least values are the two trees we just made, and Q has 5 elements: | ||
| Line 258: | Line 260: | ||
| < | < | ||
| - | Q has 4 elements: | + | ---- |
| + | |||
| + | The next two with least value, | ||
| < | < | ||
| Line 271: | Line 275: | ||
| </ | </ | ||
| - | Three items left: | + | ---- |
| + | |||
| + | The next two with least value, three items left: | ||
| < | < | ||
| Line 288: | Line 294: | ||
| </ | </ | ||
| - | Two big trees left: | + | ---- |
| + | |||
| + | The next two with least value, two big trees left: | ||
| < | < | ||
chess/programming/huffman/example.1635514882.txt.gz · Last modified: 2021/10/29 13:41 by peter