Heap Sort Algorithm in DSA Javascript - 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 find the largest element quickly, then swaps it to the end and rebuilds the heap until sorted.

beginner

What is a max heap?

A max heap is a binary tree where each parent node is greater than or equal to its children. This means the largest value is always at the root.

intermediate

Why do we rebuild the heap after swapping the root with the last element in Heap Sort?

After swapping, the heap property might break. Rebuilding (heapifying) fixes the heap so the largest element moves to the root again for the next swap.

intermediate

What is the time complexity of Heap Sort?

Heap Sort runs in O(n log n) time because building the heap takes O(n) and each of the n removals takes O(log n) to restore the heap.

advanced

How does Heap Sort differ from other sorting algorithms like Quick Sort or Merge Sort?

Heap Sort uses a heap data structure and sorts in place without extra memory. Quick Sort is faster on average but not stable. Merge Sort is stable but uses extra space.

What data structure does Heap Sort use to organize elements?

A Linked List

B Stack

C Queue

D Heap

Heap Sort uses a heap, a special binary tree structure, to organize elements for sorting.

In a max heap, where is the largest element located?

A At the root

B At the left child

C At the right child

D At the leaf nodes

The largest element in a max heap is always at the root node.

What is the main step after swapping the root with the last element in Heap Sort?

A Reverse the array

B Heapify the root to restore heap property

C Swap the first two elements

D Sort the entire array again

After swapping, heapify is done to restore the heap property starting from the root.

What is the average time complexity of Heap Sort?

A O(log n)

B O(n^2)

C O(n log n)

D O(n)

Heap Sort runs in O(n log n) time on average and in the worst case.

Which of these is true about Heap Sort?

A It sorts in place without extra memory

B It always uses extra memory

C It is unstable and uses extra memory

D It is faster than Quick Sort in all cases

Heap Sort sorts in place and does not require extra memory, unlike Merge Sort.

Explain how Heap Sort uses a max heap to sort an array step-by-step.

Think about how the largest element moves to the end each time.

Describe the difference between a max heap and a min heap and why Heap Sort uses a max heap.

Focus on the root element's value in each heap type.