Chapter 16 — Keeping Your Priorities Straight with Heaps
0.0(0)
Studied by 0 people
Call Kai
Learn
Practice Test
Spaced Repetition
Match
Flashcards
Knowt PlayCard Sorting
1/16
There's no tags or description
Looks like no tags are added yet.
Last updated 3:07 PM on 8/28/26
Name | Mastery | Learn | Test | Matching | Spaced | Call with Kai | Chat |
|---|
No analytics yet
Send a link to your students to track their progress
17 Terms
1
New cards
Heap
A tree-based structure optimized for priority access
2
New cards
Priority queue
Processes highest-priority item first
3
New cards
Max heap
A heap where the greatest value is at the root
4
New cards
Heap condition
Every parent is greater than or equal to its children
5
New cards
Weak ordering
Heap is not fully sorted; it only preserves priority order
6
New cards
Complete tree
Filled left to right with no gaps except possibly at the end
7
New cards
Read max value
O(1), because max is at the root
8
New cards
Heap insertion
Add at next open spot, then trickle up
9
New cards
Trickle up
Swap new value upward until heap condition is restored
10
New cards
Heap insertion Big O
O(log N)
11
New cards
Heap deletion
Remove root, replace with last node, then trickle down
12
New cards
Trickle down
Swap downward with larger child until heap condition is restored
13
New cards
Heap deletion Big O
O(log N)
14
New cards
Heap search
O(N), because arbitrary lookup is not the heap’s purpose
15
New cards
Array heap left child
parent index * 2 + 1
16
New cards
Array heap right child
parent index * 2 + 2
17
New cards
Array heap parent
floor((child index - 1) / 2