7.3 Insertion and Extraction | Code Scholars Tutoring

How it works

Insertion appends and sifts up; extraction takes the root, moves the last element there, and sifts down. Both cost the height of the tree.

Trace a sift by comparing only against the relevant child at each level.

Common error

Sifting down against the wrong child, which breaks the property one level below.

Worked example

Java snippets run inside a main method. Add import java.util.*; when collection types are used.

Java

PriorityQueue<Integer> q = new PriorityQueue<Integer>();
q.add(5); q.add(2); q.add(7); q.add(1);
System.out.println(q.remove());
System.out.println(q.remove());

Output

1
2

Insertion places an item at the next open leaf position and restores heap order upward. Root extraction replaces the root from the last position and restores order downward. Repeated removals expose priority order, unlike arbitrary iterator order.

Exercises

7.3.1 · Explain

Insert 1 into min-heap [2, 5, 3]. Give one resulting array after standard sift-up.

Show solution

Append 1 at index 3, swap with 5, then with 2. The resulting array is [1, 2, 3, 5].

7.3.2 · Write code

Use a min-priority queue to print 4, 1, and 2 in priority order. Explain why direct iteration is not a substitute.

Show solution

Repeated removal exposes the minimum each time; iteration does not promise sorted priority order.

One valid solution

PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
queue.add(4); queue.add(1); queue.add(2);
while (!queue.isEmpty()) System.out.print(queue.remove() + " ");

Expected output

1 2 4

Open Java compiler