UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 13.4 Free with a free account
Sorting With Priority Queues: Heap Sort
Data Structures and Algorithms · Chapter 13: Priority Queues and HeapsSection 13.4 · lesson 55 of 8710 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: Maps: Pairing Unique Keys With Their Values →← Heaps: A Complete Binary Tree That Keeps Priority OrderNext lesson: Maps: Pairing Unique Keys With Their Values →
In this lesson
Sorting an array in place using a max-heap and sift down.
- Compare priority-queue sorting with in-place heap sort in time and memory
- Trace the build and extraction phases of heap sort using sift down
- Explain why the build is linear and the total is order n log n
- Evaluate heap sort's stability and when it is the right choice
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,567 words). Read along, or search it.
Opening Question
Sorting by Taking the Largest Each Time
Picture a pile of exam papers that you want in order, from lowest score to highest. Here's a simple method. Pull out the paper with the highest score, and set it face down to start a new stack. Then pull out the highest of the rest, and lay it on top. Repeat until the pile is gone, and the new stack is sorted. The only difficulty: finding the highest paper is a long search, every time. A heap removes that difficulty. It hands back its top item in time proportional to the log of its size. So a heap can be a sorting method.
Simple Version
Sorting Through a Separate Priority Queue
The easy version uses a separate priority queue. Put every value in, then take them out one at a time. Java's PriorityQueue returns the smallest first, so the values come out in ascending order. Each add and each poll costs order log n, and there are n of each, so the sort takes order n log n time. The cost that matters here is memory. The values now exist three times over: in the original array, inside the queue, and in the output array. That's order n extra space.
Review
Max-Heap Layout in an Array
Heap sort does the same work inside the array itself. First, a quick reminder of a heap stored in an array, level by level, with no links. The children of slot i sit at two i plus one, and two i plus two. Its parent is at i minus one, over two, rounded down. In a max-heap, every parent is at least as large as its children, so slot zero holds the largest value. And the last slot that has a child is n over two, minus one.
Key Operation
Sift Down Toward the Larger Child
The key repair is sift down. When a slot holds a value that may be too small for its place, it's swapped with its larger child, again and again. These two lines find the largest of the value and its two children, checking that each child slot lies inside the heap. If the value itself is largest, the repair is finished. Otherwise it's swapped down, and the loop continues from its new slot. Each pass moves down one level, so the work is at most the height of the heap: about log two of n levels. The size parameter lets heap sort leave finished values alone.
Algorithm
Build Phase and Extraction Phase
Heap sort works in two phases. Phase one builds a max-heap from the whole array, by sifting down every slot that has a child. It works backward, from the last non-leaf slot to slot zero. Leaves are skipped, because a single value is already a heap. Going backward means the heaps below each slot are already repaired. Phase two extracts. Swap the root, the largest value, with the last slot of the heap. That value is now in its final position. Then sift down the new root, passing end as the size, so the heap is one slot shorter and the sorted values on the right are never touched. So the array always holds two regions: a shrinking heap on the left, and a growing sorted region on the right. No second array is needed.
Worked Example
Tracing Eight Values Through Heap Sort
Now run it on five, three, eight, one, nine, two, seven, four. Working backward, the build swaps one with four, leaves slot two alone, swaps three with nine, and then five with nine. That gives nine, five, eight, four, three, two, seven, one: a max-heap, with nine at the root. The first extraction swaps nine with the last slot. Nine joins the sorted region, and the one that replaced it sinks: past eight, then past seven. Eight is the new root. Each row adds the next largest value on the right: nine, then eight, then seven. After seven extractions, one value is left in the heap, and it must be the smallest.
Quick Check
One Extraction Step
Quick check. Here's a different max-heap: seven, six, three, five, one, two. The program runs one extraction step, and prints the array. Where does everything end up? Pause and predict. It prints six, five, three, two, one, then seven in the sorted region. Seven swapped places with two, the last heap slot. Then two sank: first past six, its larger child, then past five, the larger child in its new spot. Six, two, three, five, one stops after one swap, and two, six, three skips the sift down entirely. Both leave the heap rule broken.
Analysis
Why Heap Sort Is Order n Log n
Why is heap sort order n log n? Take the two phases separately. In the build, a sift down can only travel as far as the bottom. And most slots are near the bottom: about half are leaves, a quarter can move one level, an eighth two levels, and so on. Those small amounts add up to a total proportional to n. A standard analysis puts the build at no more than about two n comparisons. The extraction phase makes n minus one sift downs, each through at most about log two of n levels, with up to two comparisons per level. That's order n log n. So the total is order n plus order n log n, which is order n log n. Besides the array, only a few variables are needed: order one extra space.
Measured Results
Counting Comparisons by Input Order
A program that counts every comparison between two array elements checks this. For sixteen thousand random values, the build made thirty thousand, two hundred forty-three comparisons: below two n, which is thirty-two thousand. Extraction made over ten times as many. Does the input order matter? Random, already sorted, and reversed inputs stay within about ten percent of one another at every size. Each count is between about 1.6 and 1.85 times n log two of n, since each level of a sift down uses two comparisons. And doubling n multiplies the random count by about 2.2 each time: only a little more than doubling. That's the signature of n log n growth.
Stability
Equal Keys Can Pass Each Other
A sort is stable if records with equal keys keep their original order. That matters when data is sorted twice, say by name, then by city. Heap sort isn't stable. Swapping the root with the last slot moves a value across the whole array in one jump, so equal keys can pass one another. Six records, each a key plus a tag letter in original order, are sorted by key. Heap sort puts one E before one C, and the twos come out F, D, B, A. Java's List sort, which is stable, keeps C before E, and A, B, D, F. The remedy: record each item's original position, and compare it after the key. Then heap sort gives the stable result, at the cost of memory for the positions.
Quick Check
Five Largest of a Million Readings
Quick check. A monitoring system must report the five largest of a million readings, and it has very little spare memory. Which plan does the least work, with no second array? Pause, and decide. Build a max-heap in place, then do just five extractions. The build is about order n, and each extraction is order log n, so about n plus five log n in all. A full heap sort does all the extractions, order n log n, only to use five of them. And a priority-queue sort needs a whole second array, which this system can't spare.
Measured Results
Top Three Versus a Full Sort
Measured on ten thousand random values: building the heap and taking out the top three cost eighteen thousand, eight hundred nineteen comparisons. The full sort cost two hundred thirty-five thousand, about twelve times as much. And the three values match the ones a full sort finds. In general, the top k items cost about order n plus k log n.
When to Use It
Guaranteed Time, Constant Memory
So when is heap sort chosen? It's rarely the fastest on ordinary data, but its mix of properties is hard to find elsewhere. Quicksort can slow down badly on unlucky input, and merge sort normally needs a second array. Heap sort guarantees order n log n time, with constant extra memory. Library sorts sometimes keep one in reserve. In OpenJDK twenty-one, the sorting code for primitive arrays contains a private heap sort, used when its quicksort recurses too deep. On the other side, heap sort jumps around memory, since a parent and its children sit far apart. On big ordinary data, tuned quicksort or merge sort is often faster. And if equal keys must keep their order, heap sort alone won't do: add a tie-breaker, or choose a stable sort.
Common Mistakes
Direction, Shrinking and Heap Type
Common mistakes. Building in the wrong direction: sift down must run from the last non-leaf slot back to slot zero. Forgetting to shrink the heap: given the full length, sift down pulls the sorted values back in. Using a min-heap and expecting ascending order: moving the smallest to the end leaves the array descending. And thinking the build dominates. It costs about two n comparisons. The extractions are what make the total n log n.
Key Takeaways
Heap Sort in Two Phases
To sum up. A priority queue sorts by taking every item in, then removing them one by one: order n log n time, but order n extra memory. Heap sort does the same inside the array. Build a max-heap, then repeatedly swap the root with the last heap slot, shrink the heap, and sift down. The build takes about two n comparisons and the extractions order n log n, for any input order, in constant extra space. Heap sort isn't stable, but it guarantees its time, and can stop early to find the top k items.
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 Sorting With Priority Queues: Heap Sort
How does heap sort work?
What is the time and space complexity of heap sort?
Is heap sort stable?
Why would you choose heap sort over quicksort or merge sort?
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 →