=========================================================================== * Restore the heap property by moving down the tree starting at node k, * exchanging a node with the smallest of its two sons if necessary, stopping * when the heap property is re-established (each father smaller than its * two sons). */
(s, tree, k)
| 452 | * two sons). |
| 453 | */ |
| 454 | local void pqdownheap(s, tree, k) |
| 455 | deflate_state* s; |
| 456 | ct_data* tree; /* the tree to restore */ |
| 457 | int k; /* node to move down */ |
| 458 | { |
| 459 | int v = s->heap[k]; |
| 460 | int j = k << 1; /* left son of k */ |
| 461 | while (j <= s->heap_len) |
| 462 | { |
| 463 | /* Set j to the smallest of the two sons: */ |
| 464 | if (j < s->heap_len && |
| 465 | smaller(tree, s->heap[j+1], s->heap[j], s->depth)) |
| 466 | { |
| 467 | j++; |
| 468 | } |
| 469 | /* Exit if v is smaller than both sons */ |
| 470 | if (smaller(tree, v, s->heap[j], s->depth)) break; |
| 471 | |
| 472 | /* Exchange v with the smallest son */ |
| 473 | s->heap[k] = s->heap[j]; |
| 474 | k = j; |
| 475 | |
| 476 | /* And continue down the tree, setting j to the left son of k */ |
| 477 | j <<= 1; |
| 478 | } |
| 479 | s->heap[k] = v; |
| 480 | } |
| 481 | |
| 482 | /* =========================================================================== |
| 483 | * Compute the optimal bit lengths for a tree and update the total bit length |