Heap Sort Algorithm in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the Heap Sort algorithm?

Heap Sort uses a special tree structure called a heap to sort elements. It builds a max-heap to repeatedly extract the largest element and place it at the end of the array, sorting the array in ascending order.

beginner

What is a max-heap?

A max-heap is a complete binary tree where each parent node is greater than or equal to its child nodes. This property helps quickly find the largest element at the root.

intermediate

What are the two main steps in Heap Sort?

1. Build a max-heap from the input array.<br>2. Repeatedly swap the root (largest) with the last element, reduce heap size, and heapify the root to maintain max-heap.

intermediate

What is the time complexity of Heap Sort and why?

Heap Sort runs in O(n log n) time because building the heap takes O(n), and each of the n elements is extracted with a heapify operation costing O(log n).

beginner

Why is Heap Sort considered an in-place sorting algorithm?

Heap Sort sorts the array without needing extra space for another array. It rearranges elements within the original array, using only a small amount of extra memory for variables.

What data structure does Heap Sort use to organize elements?

A Linked List

B Queue

C Heap

D Stack

Heap Sort uses a heap, specifically a max-heap, to organize elements for sorting.

In Heap Sort, what is the root of the max-heap?

A Smallest element

B Random element

C Middle element

D Largest element

The root of a max-heap is always the largest element.

What is the time complexity of Heap Sort in the average case?

A O(n log n)

B O(n^2)

C O(log n)

D O(n)

Heap Sort runs in O(n log n) time on average.

Which step is NOT part of Heap Sort?

A Sorting by insertion

B Swapping root with last element

C Building a max-heap

D Heapifying the root

Heap Sort does not use insertion sort; it uses heap operations.

Heap Sort is considered an in-place algorithm because:

A It uses extra arrays

B It sorts without extra space

C It uses recursion

D It uses linked lists

Heap Sort sorts the array within the original space without needing extra arrays.

Explain the process of building a max-heap from an unsorted array.

Think about fixing the heap from bottom to top.

Describe how Heap Sort extracts elements to produce a sorted array.

Focus on how the largest element moves to the end each time.