UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 13.3 Free with a free account
Heaps: A Complete Binary Tree That Keeps Priority Order
Data Structures and Algorithms · Chapter 13: Priority Queues and HeapsSection 13.3 · lesson 54 of 879 min · free with a free account
Free preview
Create a free account to keep watching
It takes a minute and costs nothing. Your free account unlocks all of Chapter 1 and 3 more lessons of Data Structures and Algorithms.
Lesson complete
Earn the 3 college credits for Data Structures and Algorithms
Enrolling adds a quiz after each lesson, the graded work and the official transcript. Recommended for credit by NCCRS.
Next lesson: Sorting With Priority Queues: Heap Sort →← Building a Priority Queue in Java, Step by StepNext lesson: Sorting With Priority Queues: Heap Sort →
In this lesson
How heap order and a complete shape make priority queues fast.
- State the heap-order and complete-shape rules and what each provides
- Locate parents and children in an array-based heap by index arithmetic
- Trace up-heap after insertion and down-heap after removing the minimum
- Explain why bottom-up heap construction runs in linear time
Free study notes
Get this lesson's notes by email
The key points and 4 practice questions with answers, in your inbox. One email, free.
One email. Unsubscribe in one click.
Transcript
Everything said in the video, section by section (1,365 words). Read along, or search it.
Opening Question
Making Both Jobs Fast
A priority queue must do two jobs over and over: add an item, and remove the most urgent one. Here, a smaller number means more urgent. Store the items in an unsorted array, and adding is instant, but finding the minimum means scanning everything. Keep the array sorted, and the minimum is right there, but every new item must be slotted in, shifting the others. Each simple choice makes one job slow. Is there a structure that makes both fast? There is, and Java's PriorityQueue is built on it.
Definition
Heap Order and Complete Shape
A heap is a binary tree that obeys two rules at the same time. The first is heap order: every item is smaller than or equal to its children. That puts the smallest item at the root. A max-heap simply flips the rule, so the largest is on top. The second rule is a complete shape: every level is full except possibly the last, and the last fills from left to right, with no gaps. This tree breaks heap order, because nine sits above four. And this one breaks the shape, because the last level has a gap. A heap needs both rules, all the time.
Key Insight
Partial Order and a Short Tree
Each rule has its own job. Heap order keeps the minimum at the root, so looking at it costs one step. But heap order is weaker than sorting. It only compares a parent with its own children. Items in different branches aren't ordered against each other. The reverse does hold: an array sorted from smallest to largest is always a valid min-heap. The complete shape keeps the tree short. Seven items take two levels below the root, a thousand take nine, and a million only nineteen. Every operation here follows one path, so that small height is the cost.
Array Layout
Parent and Child Index Arithmetic
Because the shape has no gaps, the items can be written into an array level by level, left to right, and nothing is lost. No links are needed. A node's relatives come from arithmetic on its index. The parent of i is i minus one, over two, and its children are two i plus one, and two i plus two. Take index two, holding ten. Its parent is index zero, and its children are indexes five and six: sixty and fifty. One more detail matters: the last item in the array is always the last node of the bottom level. Adding at the end, or taking the last item away, never breaks the shape.
Java Example
Printing Shows the Heap Array
That's why printing a Java priority queue shows its array, not a sorted list. Add forty, twenty-five, sixty, ten, thirty, five and fifty, and it prints this very heap. Removing the items one at a time still returns them in order: five, ten, twenty-five, and so on.
Insertion
Up-Heap Bubbling
To add an item, put it in the first free slot. That keeps the shape complete. But the new item may be smaller than its parent, breaking heap order. The repair is called up-heap, or bubbling up: while the item is smaller than its parent, swap the two. Add five to this heap. It lands at index five, under sixty. Five is smaller, so they swap. Now five sits at index two, under ten. Smaller again, so they swap, and five reaches the root. Two swaps, and the heap is valid again.
Cost
Swaps Bounded by Height
Why is that order log n? Each swap moves the new item up exactly one level, and it never moves down. So it can make at most as many swaps as the heap is tall. In a test with one thousand twenty-three items, each smaller than all those before it, the worst case, no insertion took more than nine swaps: the height of that heap. Many insertions are much cheaper. Building the heap from forty, twenty-five, sixty, ten, thirty, five and fifty took five swaps in total, and four of the seven insertions needed none.
Quick Check
Adding Three to a Min-Heap
Quick check. Here's a new min-heap: five, nine, seven, twelve, ten, eight, eleven. Add three to it. How many swaps does up-heap make? Pause, and decide. It's c: three swaps. Three lands at index seven, under twelve, and swaps with it. Then it swaps with nine, and then with five, which puts it at the root. The array becomes three, five, seven, nine, ten, eight, eleven, twelve. One swap would be enough only if three were bigger than nine. It climbs the whole height, because it's the new minimum.
Removal
Down-Heap Sinking
Removing the minimum takes the root, and leaves a hole at the top. Shifting everything would be slow, and any other choice would break the shape. The trick: take the last item of the array, which can leave without disturbing the shape, and move it into the root. Now the shape is right, but the item at the root is probably too large. The repair is down-heap, or sinking: while it's larger than a child, swap it with the smaller child. Remove five from our heap. Fifty moves to the root. Its children are twenty-five and ten. Ten is smaller, so they swap, and the heap is valid after one swap.
Key Rule
Swap With the Smaller Child
Why the smaller child? Take the heap twelve, five, seven, nine, ten, eight, eleven, just after the move. Twelve has children five and seven. Swap with the larger child, seven, and five ends up below seven: heap order is broken. Swap with five, the smaller one, and five sits on top, not larger than anything below it. Down-heap is order log n for the same reason as up-heap: one level per swap. In the same thousand-item test, the most swaps for a single removal was eight.
Construction
Bottom-Up Heap Building
Suppose all n items are in hand at once. Adding them one at a time costs up to log n each. There's a faster way, called bottom-up construction. Copy the items into the array as they are. The shape is already complete; only heap order may be wrong. Then run down-heap on the last item that has a child, at index n over two, minus one, and move left, one index at a time, finishing at the root. Take forty, twenty-five, sixty, ten, thirty, five, fifty. Index two: sixty sinks below five. Index one: twenty-five swaps with ten. Index zero: forty swaps with five. Three swaps, against five for adding one at a time. The result differs from the earlier heap, and both are valid: the same items can form more than one heap.
Cost
Why Bottom-Up Is Linear
Why is that order n, not n log n? A node can sink at most its height above the bottom, and most nodes are near the bottom. In a tree of fifteen nodes, eight are leaves and cost nothing. Four can sink one level, two can sink two, and the root can sink three. That's at most eleven swaps, fewer than fifteen. Measured with the worst input, a descending list, one thousand twenty-three items took eight thousand one hundred ninety-four swaps one at a time, and only one thousand thirteen bottom-up.
Quick Check
Building From Nine, Four, Seven, One
Quick check. Build a min-heap bottom-up from the array nine, four, seven, one. What array do you end up with? Pause, and predict. It's a. With four items, start at index one: four sinks below one. Then index zero: nine swaps with one, and keeps sinking, below four. Option b stops nine after one swap, but nine is still above four. Option c runs the indexes forward, from the root down, and leaves one below four.
Key Takeaways
Order, Shape and Repairs
To recap. A heap obeys heap order, parent no larger than its children, and a complete shape, with no gaps. Order puts the minimum at the root, readable in constant time. The shape lets the heap live in an array, with parent at i minus one over two, and children at two i plus one and two i plus two. Up-heap repairs an insertion and down-heap repairs a removal, each order log n, always swapping with the smaller child on the way down. And building bottom-up costs only order n, because most nodes sit near the bottom.
Think About It
Where the Largest Item Hides
Here's something to think about. In a min-heap of a million items, where can the largest item be? How many places might you have to look, and what does that say about using a min-heap to find a maximum?
About Data Structures and Algorithms at UPI Study
Data Structures and Algorithms (Computer Science 251) is a self-paced online course of 87 video lessons in 17 chapters, from Java and object-oriented design to arrays, linked lists, recursion, stacks and queues, trees, heaps, hash tables, sorting and graphs. It carries a NCCRS credit recommendation for 3 semester credits.
Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →
Compare: Discrete Math vs Data Structures and Algorithms · Intro to Java vs Data Structures and Algorithms
Why take it here
Why students take Data Structures and Algorithms with UPI Study
Where the credit goes
Universities that work with NCCRS
Data Structures and Algorithms carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Thomas Edison State UniversitySigned partner
University of the PeopleSigned partner
Charter Oak State CollegeSigned partner
Strayer UniversitySigned partner
Columbia Southern UniversitySigned partner
Indiana TechSigned partner
Penn StateWorks with NCCRS
Southern New Hampshire UniversityWorks with NCCRS
SUNYWorks with NCCRS
+many more cooperating universitiesFind my college →Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.
FAQ
Questions students ask us
About Heaps: A Complete Binary Tree That Keeps Priority Order
What is a binary heap?
How do you insert into a min-heap?
Why does down-heap swap with the smaller child?
Why is bottom-up heap construction O(n) instead of O(n log n)?
About the Data Structures and Algorithms course
How many college credits is Data Structures and Algorithms?
How much does Data Structures and Algorithms cost and what is included?
Which universities accept UPI Study credits?
How long does Data Structures and Algorithms take?
How are the exams done?
How do my credits reach my college?
Ready for the full course? Earn 3 credits in Data Structures and Algorithms.
87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.
3 credits · NCCRSEnroll →