=========================================================================== * 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). */
| 505 | * two sons). |
| 506 | */ |
| 507 | local void pqdownheap(deflate_state *s, ct_data *tree, int k) { |
| 508 | int v = s->heap[k]; |
| 509 | int j = k << 1; /* left son of k */ |
| 510 | while (j <= s->heap_len) { |
| 511 | /* Set j to the smallest of the two sons: */ |
| 512 | if (j < s->heap_len && |
| 513 | smaller(tree, s->heap[j + 1], s->heap[j], s->depth)) { |
| 514 | j++; |
| 515 | } |
| 516 | /* Exit if v is smaller than both sons */ |
| 517 | if (smaller(tree, v, s->heap[j], s->depth)) break; |
| 518 | |
| 519 | /* Exchange v with the smallest son */ |
| 520 | s->heap[k] = s->heap[j]; k = j; |
| 521 | |
| 522 | /* And continue down the tree, setting j to the left son of k */ |
| 523 | j <<= 1; |
| 524 | } |
| 525 | s->heap[k] = v; |
| 526 | } |
| 527 | |
| 528 | /* =========================================================================== |
| 529 | * Compute the optimal bit lengths for a tree and update the total bit length |