=========================================================================== * 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). */
| 446 | * two sons). |
| 447 | */ |
| 448 | local void pqdownheap(deflate_state *s, ct_data *tree, int k) |
| 449 | { |
| 450 | int v = s->heap[k]; |
| 451 | int j = k << 1; /* left son of k */ |
| 452 | while (j <= s->heap_len) { |
| 453 | /* Set j to the smallest of the two sons: */ |
| 454 | if (j < s->heap_len && |
| 455 | smaller(tree, s->heap[j+1], s->heap[j], s->depth)) { |
| 456 | j++; |
| 457 | } |
| 458 | /* Exit if v is smaller than both sons */ |
| 459 | if (smaller(tree, v, s->heap[j], s->depth)) break; |
| 460 | |
| 461 | /* Exchange v with the smallest son */ |
| 462 | s->heap[k] = s->heap[j]; k = j; |
| 463 | |
| 464 | /* And continue down the tree, setting j to the left son of k */ |
| 465 | j <<= 1; |
| 466 | } |
| 467 | s->heap[k] = v; |
| 468 | } |
| 469 | |
| 470 | /* =========================================================================== |
| 471 | * Compute the optimal bit lengths for a tree and update the total bit length |