=========================================================================== * 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)
| 453 | * two sons). |
| 454 | */ |
| 455 | local void pqdownheap(s, tree, k) |
| 456 | deflate_state *s; |
| 457 | ct_data *tree; /* the tree to restore */ |
| 458 | int k; /* node to move down */ |
| 459 | { |
| 460 | int v = s->heap[k]; |
| 461 | int j = k << 1; /* left son of k */ |
| 462 | while (j <= s->heap_len) { |
| 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 | j++; |
| 467 | } |
| 468 | /* Exit if v is smaller than both sons */ |
| 469 | if (smaller(tree, v, s->heap[j], s->depth)) break; |
| 470 | |
| 471 | /* Exchange v with the smallest son */ |
| 472 | s->heap[k] = s->heap[j]; k = j; |
| 473 | |
| 474 | /* And continue down the tree, setting j to the left son of k */ |
| 475 | j <<= 1; |
| 476 | } |
| 477 | s->heap[k] = v; |
| 478 | } |
| 479 | |
| 480 | /* =========================================================================== |
| 481 | * Compute the optimal bit lengths for a tree and update the total bit length |