Algoritmika 2026/27 sügis

HW4. Heaps, Priority Queues, and Succinct Trees

Version: 2026-09-06

Deadline: Monday, 28.09.2026, 23:59

Purpose

Heaps maintain enough order to expose the minimum without sorting everything. This homework studies why bottom-up construction is linear, how heap arity changes upward and downward work, and how an unbalanced binary tree can be stored as a compact shape bit vector.

Use zero-based array indexing throughout. State exactly what counts as one key comparison and one moved item or swap.

Expected workload: approximately 6-8 hours for the five base tasks. Bonus tasks are not included.

General requirements

• Check every heap automatically after construction and updates.
• Use identical input arrays for methods being compared.
• Record random seeds and exclude input generation from measured time.
• Keep instrumented comparison counts separate from uninstrumented timing runs.
• Aim for a concise report of approximately 3-5 pages, excluding code and optional appendices.

Base tasks

T1. How difficult can bottom-up heapify be? (1p, approachable)

Using every integer from 0 through 14 exactly once, construct an input array that causes Floyd's bottom-up binary min-heapify to perform as many swaps as possible.

Use the standard sift-down rule: compare the two children, continue through the smaller child, and swap only when the parent is larger. Process internal array positions from 6 down to 0.

1. Show the array before heapify and after each internal position is processed.
2. Count key comparisons and swaps, and verify the final heap invariant.
3. Derive an upper bound on the number of swaps from the possible downward movement in the 3-, 7-, and 15-node subheaps.
4. Prove that your input reaches this bound and is therefore as difficult as possible under this counting convention.
5. Insert the same values, in the same order, into an initially empty binary min-heap. Compare the resulting heap and the number of comparisons and swaps with bottom-up construction.

Deliverable: adversarial input, seven-row bottom-up trace, final heaps and counts for both construction methods, invariant checks, upper bound, and at most 140 words of argument and comparison.

T2. Construct a left-heavy min-heap (1p, conceptual)

Using every integer from 1 through 20 exactly once, construct a complete binary min-heap satisfying this additional condition at every node with two nonempty subtrees:

sum(all keys in the left subtree) > sum(all keys in the right subtree)

The sums include every descendant on the relevant side, not only the immediate child. Give a table containing only the nodes that have two children and verify both conditions automatically.

Give an insertion order that makes standard heap insertion produce exactly your final array. Explain why inserting the entries of any valid heap array from left to right does not require a swap.

Deliverable: final array and tree, compact subtree-sum table, insertion order, automatic replay, and at most 120 words of argument.

T3. Heapify, sorting, and draining a heap (1p, experimental)

Test these three operations on identical random permutations of distinct integers:

1. Python heapq.heapify only;
2. Python sorted;
3. heapq.heapify followed by repeated heappop until the heap is empty.

Use at least four increasing input sizes, including n = 1_000_000 if it fits in memory without paging, and at least five repetitions per size. Prepare independent input copies before starting the timer. Time only the operation being compared, not data generation or copying. Verify that methods 2 and 3 produce the same sorted result.

Before measuring, predict the relative growth and order of the three running times. Find the smallest tested size at which heapify is faster than sorting. If none of the tested sizes shows this, report that result and investigate rather than hiding it.

Explain why bottom-up heapify is Theta(n) but emptying the heap with n calls to extract-min is Theta(n log n). Thus heapify followed by draining is a sorting method, while heapify alone is not.

Deliverable: sizes and environment, median timing table and one plot, crossover result, correctness check, and at most 160 words connecting the measurements with the asymptotic bounds.

T4. Which heap arity works for a streaming top-m filter? (1p, experimental)

A stream may be too large to sort or retain in memory, but we need its m largest values. Maintain a k-ary min-heap containing only the best m values seen so far. The root is the smallest retained value:

collect the first m values and heapify them
for each later value x:
    compare x with the root
    if x is larger:
        replace the root with x
        sift the new root down

Implement bottom-up heapify and root replacement for a configurable array-based k-ary min-heap. Derive and test the zero-based parent and child index formulas. Use k = 2, 3, 4, 8, 16, m = 100, 10_000, and N = 1_000_000 stream values.

Use the three generators below. For this controlled experiment, materialise one sequence for each (generator, m, seed) case and reuse exactly those values for every k; exclude generation from timing. The spread is scaled with m so that the two heap sizes receive meaningful but not identical workloads. Compare arities only on identical streams.

import random


def stream_a(n, keep, seed=2026):
    rng = random.Random(seed)
    spread = 50.0 * keep
    for _ in range(n):
        yield round(rng.gauss(0.0, spread))


def stream_b(n, keep, seed=2026):
    rng = random.Random(seed)
    spread = 50.0 * keep
    level = 0.0
    for _ in range(n):
        level += 20.0
        yield round(level + rng.gauss(0.0, spread))


def stream_c(n, keep, seed=2026):
    rng = random.Random(seed)
    spread = 50.0 * keep
    level = 0.0
    velocity = 20.0
    for i in range(n):
        if i > 0 and i % 4096 == 0:
            velocity = 0.85 * velocity + 0.15 * 20.0 + rng.gauss(0.0, 12.0)
        level += velocity
        yield round(level + rng.gauss(0.0, spread))

Before running the experiment, inspect the generators and predict for each one whether accepted replacements will become rarer, remain sustained, or occur in active and quiet periods. Also predict how increasing k changes heap height and the child comparisons needed by one root replacement. Preserve this prediction in the report.

For every (generator, m, k) case, record:

• root comparisons and accepted replacements;
• child comparisons and moved items;
• total elapsed processing time;
• accepted replacements in each consecutive block of 10,000 stream values.

Use seed 2026 for the complete comparison. Rerun only the two most promising arities with seeds 2027 and 2028 to check whether the recommendation is stable. Verify every final retained multiset against sorted(stream)[-m:] outside the timed section. Check the heap invariant after every replacement on a small prefix and at the end of every full run.

For a fixed (generator, m, seed), every correct arity must accept exactly the same stream positions and return the same final multiset. Treat disagreement as a correctness failure, not an experimental result.

Recommend an arity separately for each workload, or state that arity has no meaningful effect when most values are rejected at the root. Explain how temporal distribution, heap size, and the frequency of expensive root replacements affect the result.

Deliverable: formulas and tested implementation, prediction table, compact comparison table, one plot showing blockwise accepted replacements, correctness checks, recommendations, and at most 220 words of interpretation.

T5. Encode an HW3 search tree in 2n+1 bits (1p, conceptual)

Build the ordinary unbalanced BST obtained by inserting this 14-value Collatz-59 prefix from HW3:

59, 178, 89, 268, 134, 67, 202, 101, 304, 152, 76, 38, 19, 58

Encode its exact binary-tree shape in breadth-first order. Write 1 for a real node and 0 for a missing child: first emit 1 for the root, then process every real node in breadth-first order and emit its left-child bit followed by its right-child bit. Missing children are not processed further. A tree with n real nodes therefore uses 2n+1 bits.

Store the keys separately in breadth-first order. Using one-based bit positions, let rank1(x) count the 1-bits through position x and let select1(i) locate the i-th 1-bit. If a real node is at bit position x, its breadth-first node number is i = rank1(x) and its child bits are at positions 2i and 2i+1.

Use your encoding to locate both children of key 89, identify which side of key 67 contains key 76, and recover the parent of key 76. Explain how rank1 and select1 translate between bit positions and entries in the separate key array.

Deliverable: tree drawing, 29-bit shape vector, breadth-first key array, the three navigation traces, and at most 120 words explaining what space the shape vector saves and what it does not store. Code may be used to verify the answer but is not required.

Bonus tasks

Choose one of the following two levels. B2 includes the required reading and is worth 2 bonus points in total; B1 and B2 do not stack to 3 points.

B1. Read and evaluate the B-heap paper (bonus 1p)

Read Poul-Henning Kamp, You're Doing It Wrong and inspect the accompanying original figures, data, simulator, and source code.

Answer these questions concisely:

1. Why can vertical movement through an ordinary array-based binary heap touch many virtual-memory pages or cache regions?
2. How does the B-heap layout change locality, and what extra work can it introduce?
3. Reconstruct the paper's principal workload and memory-model parameters. Identify one reported situation in which the B-heap wins and one in which it loses.
4. Which asymptotic bounds remain unchanged? Explain why the paper's result does not contradict comparison-based heap analysis.
5. Identify one assumption or claim that should be retested on a current computer, and propose a measurement for it.

Deliverable: at most two pages containing one small layout diagram, direct answers to the five questions, and a complete citation. Do not submit a general summary of the article.

B2. Implement and test the B-heap (bonus 2p)

After completing the reading required for B1, implement a configurable B-heap and a conventional binary heap with the same priority-queue interface and comparable implementation quality. Derive and test the B-heap parent/child mapping rather than treating the original C source as a black box.

Reproduce the structure of Kamp's workload: insert n items, alternate one extraction and one insertion for n rounds while keeping the queue near size n, and finally drain it. Use identical pre-generated keys and operations for both layouts. Test at least three increasing sizes, including one that exceeds the relevant cache level if your environment permits it, and several block capacities.

Record key comparisons, moved items, running time, and memory assumptions. In addition, record logical block accesses or simulate a bounded LRU set of resident blocks so that locality is measured even when the operating system does not create observable page faults. Keep instrumented and timing runs separate.

Validate every extracted key against a trusted reference and check the heap invariant after every operation on small cases. Explain where the B-heap begins to help, or report honestly that no practical crossover was observed on your system.

Deliverable: implementation and mapping tests, reproducible generator and seeds, correctness checks, compact results and plots, comparison with the paper's findings, and at most 300 words of conclusions.

AI use for this homework

• T1, T2, and T5: Produce the trace, construction, and navigation reasoning independently. AI may help check the finished result.
• T3 and T4: AI may help with implementation, debugging, and plotting. Make the prediction and interpret the measurements yourself.
• Disclose substantial AI assistance and be prepared to explain all submitted code and conclusions.

Submission checklist

• Indexing and counting conventions are explicit.
• Every heap output is checked automatically.
• Timing comparisons use identical data and exclude generation.
• The succinct bit vector is distinguished from its key array and any navigation index.
• Report and code/source files are uploaded separately.