CodeBlanks Logo Icon CodeBlanks
Login Register

Extract

Remove the root, move the last up, sift down.

Extract

When extracting the root (smallest) from a heap: the last element moves to the root, the heap shrinks by one, then sift-down is done.

Sift-down: if the root is smaller than its children stop; otherwise swap with the smaller child and go down. Stop at a leaf.

Extraction is O(log n): root swap O(1) + sift-down O(log n).

Sift-down detail

Sift-down: i is the root index. Left and right children are computed. The smaller child is found. If arr[i] is larger than the smaller child, swap, set i = smaller child index, repeat.

Stop at a leaf (no children) or when <= both children. The min-heap property is restored.

Each swap goes down one level; at most log n swaps.

Practice Sift-down (extract)

Write sift_down(arr, n, i). Sift down for a min-heap. Print [1, 3, 2] with arr = [3, 1, 2]; sift_down(arr, 3, 0); print(arr).

Starter code

solution.py
def sift_down(arr, n, i):
    # Sift down

Sample solution

solution.py
def sift_down(arr, n, i):
    # Sift down
    smallest = i
    left = 2 * i + 1
    right = 2 * i + 2
    if left < n and arr[left] < arr[smallest]:
        smallest = left
    if right < n and arr[right] < arr[smallest]:
        smallest = right
    if smallest != i:
        arr[i], arr[smallest] = arr[smallest], arr[i]
        sift_down(arr, n, smallest)
arr = [3, 1, 2]
sift_down(arr, 3, 0)
print(arr)

Expected output

[1, 3, 2]

Questions and answers

Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.

1 Extract: match the terms

Term Meaning
Extract Take root
Sift-down Shift down
Smaller child Swap
Cost O(log n)

2 Which child does sift-down swap with?

  • The larger one
  • Right always
  • Left always
  • The smaller one Correct answer

Explanation: The smaller one

3 Sift-down condition

Question 
if arr[smallest] ____arr[i]:
Answer 
if arr[smallest] <arr[i]:

Explanation: < is right.

All lessons in Intermediate

1 Merge sort

  1. Divide and conquer
  2. Merge operation
  3. Full merge sort
  4. Summary - Merge sort

2 Quick sort

  1. Pivot selection
  2. Partitioning
  3. Recursive quick sort
  4. Summary - Quick sort

3 Heap sort

  1. What is a heap?
  2. Heapify
  3. Build heap and sort
  4. Summary - Heap sort

4 Counting sort

  1. Counting idea
  2. Count array
  3. Output array
  4. Summary - Counting sort

5 Radix sort

  1. Radix idea
  2. Digit pass
  3. Stable sub-sort
  4. Summary - Radix sort

6 Sorting project

  1. Project: Overview
  2. Score array
  3. Apply merge sort
  4. Print statistics

7 Tree

  1. What is a tree?
  2. Node and edge
  3. Binary tree
  4. Summary - Trees

8 Binary search tree

  1. BST rule
  2. BST insert
  3. BST search
  4. Summary - BST

9 AVL tree

  1. Balanced tree
  2. Rotation
  3. Balance after insert
  4. Summary - AVL tree

10 Heap

  1. Min and max heap
  2. Insert
  3. Extract
  4. Summary - Heap

11 Priority queue

  1. What is a priority queue?
  2. Heap-based implementation
  3. Push and pop
  4. Summary - Priority queue

12 Data structures project

  1. Project: Overview
  2. Undo stack
  3. Pending queue
  4. Print the state

13 Graph basics

  1. What is a graph?
  2. Adjacency list
  3. Adjacency matrix
  4. Summary - Graph

14 Breadth-first search

  1. BFS idea
  2. Using a queue
  3. Marking visited
  4. Summary - BFS

15 Depth-first search

  1. DFS idea
  2. Stack or recursion
  3. Backtracking
  4. Summary - DFS

16 Greedy algorithms

  1. Greedy approach
  2. Coin change
  3. Greedy limits
  4. Summary - Greedy

17 Divide and conquer

  1. Three steps
  2. Recursive structure
  3. Master theorem
  4. Summary - Divide and conquer

18 Backtracking

  1. What is backtracking?
  2. State tree
  3. Pruning
  4. Summary - Backtracking

19 Graph project

  1. Project: Overview
  2. City graph
  3. BFS for reachability
  4. Print the result

20 Intermediate final

  1. Challenge 1
  2. Challenge 2
  3. Challenge 3
  4. Challenge 4