# Heaps and Priority Management

Computer Science I · Data Structures · https://tryals.app/learn/computer-science-i/heaps-and-priority-management

## Always Serving the Most Urgent

Sometimes you need the **most important** item first, not the oldest. A **priority queue** serves elements by **priority** rather than arrival. The structure that implements it efficiently is the **binary heap**.

A binary heap is a **complete binary tree** (filled level by level, left to right) satisfying the **heap property**:

| Heap Type | Root Element | Parent-Child Rule |
| --- | --- | --- |
| **Max-Heap** | Maximum | Parent $\ge$ Children |
| **Min-Heap** | Minimum | Parent $\le$ Children |

The extreme element is always available in $O(1)$ time at the top.

## Operations and Layout

Insertion and removal maintain the heap property via **sifting** in $O(\log n)$ time:

- **Insert**: Place at the next open leaf, then **sift up** (swap with parent while larger).
- **Remove**: Take root, move last leaf there, then **sift down** (swap with larger child).

Because the tree is complete, store it in a plain **array**: node $i$ has children at $2i+1$ and $2i+2$.

> **Common pitfall:** Expecting a heap to be **fully sorted**. It is only **partially ordered**—parents relate to children, but siblings and cousins are unordered. Heaps give fast access to the extreme element, powering Dijkstra's and **heapsort**.

## Practice questions

4 of this lesson's 10 practice questions, with answers. The full set is in the app.

### 1. Select every statement the lesson supports about binary heaps.

A. A heap can be stored in a plain array with no pointers
B. The extreme element is available at the root in O(1)
C. A heap keeps its elements fully sorted
D. Insertion and removal are both O(log n)
E. In a max-heap every parent is at least as large as its children

**Answer:** A. A heap can be stored in a plain array with no pointers; B. The extreme element is available at the root in O(1); D. Insertion and removal are both O(log n); E. In a max-heap every parent is at least as large as its children

**Why:** Constant-time access to the extreme, logarithmic updates, array storage and the parent-child relation are all stated. Full sorting is not: the property relates parents to children only, leaving siblings and cousins unordered, expecting a sorted sequence is the pitfall the lesson names, and getting one requires repeatedly removing the root.

Page: https://tryals.app/practice/computer-science-i/heaps-and-priority-management/select-every-statement-the-lesson-supports-about-binary-heaps

### 2. A binary heap is far weaker than a binary search tree: it only guarantees each parent beats its children, so it cannot search for an arbitrary value in better than O(n). Why is that weaker invariant an advantage rather than a defect?

A. Because finding the maximum only needs the root.
B. Because a heap converts to a BST in constant time.
C. Because the heap invariant is stronger than the BST one.
D. Because heaps are only used for small collections.

**Answer:** A. Because finding the maximum only needs the root.

**Why:** A priority queue is asked for the highest-priority item and nothing else, and the heap property puts it at the root by construction. Being weaker pays twice: restoring the invariant means sifting one node up a single path, and because left and right are unconstrained the tree stays complete and lives in a flat array. The best invariant is the weakest one that still works.

Page: https://tryals.app/practice/computer-science-i/heaps-and-priority-management/a-binary-heap-is-far-weaker-than-a-binary-search-tree-it-only

### 3. The value 45 is inserted into the max-heap stored as 50, 30, 40, 10, 20, 35, 25. Order what happens.

**Answer:**

1. 45 is placed at the next open leaf, index 7, below the node holding 10
2. 45 is compared with its parent 10 and, being larger, swaps with it
3. 45 is now at index 3 and is compared with its parent 30
4. 45 is larger than 30, so they swap and 45 arrives at index 1
5. 45 is compared with the root 50, is smaller, and stops there

**Why:** The new value enters at the bottom and climbs only while it beats its parent, stopping under 50. Two swaps suffice, and in general the climb is at most the height of the tree, which is why insertion is logarithmic rather than linear despite touching the whole path.

Page: https://tryals.app/practice/computer-science-i/heaps-and-priority-management/the-value-45-is-inserted-into-the-max-heap-stored-as-50-30-40-10

### 4. A binary heap lives in a flat array with no pointers at all, and children are found by arithmetic. Which property of the heap makes that possible?

A. That heaps store only numbers, which can be packed contiguously
B. That heaps are always balanced, unlike binary search trees
C. Completeness, so positions can be numbered without gaps
D. The heap property, which orders parents above children

**Answer:** C. Completeness, so positions can be numbered without gaps

**Why:** Shape does the work, not order: no gaps means level-order numbering is dense, so children sit at 2i+1 and 2i+2 by arithmetic. A BST has no shape guarantee, so it needs pointers, and that is why a heap has the memory profile of an array while behaving like a tree.

Page: https://tryals.app/practice/computer-science-i/heaps-and-priority-management/a-binary-heap-lives-in-a-flat-array-with-no-pointers-at-all-and