Heap sort algorithm in Data Structures Theory - 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 heap from the data, then repeatedly removes the largest (or smallest) item and rebuilds the heap until all items are sorted.

beginner

What type of heap is typically used in Heap sort to sort in ascending order?

A max-heap is used. It keeps the largest element at the root, so the algorithm can remove the largest element first and place it at the end of the sorted list.

intermediate

What is the time complexity of Heap sort in the average and worst cases?

Heap sort runs in O(n log n) time for both average and worst cases, where n is the number of elements to sort.

intermediate

How does Heap sort differ from Quick sort in terms of memory usage?

Heap sort is an in-place sorting algorithm, meaning it sorts the data without needing extra space. Quick sort also sorts in-place but can use more stack space due to recursion.

intermediate

Why is Heap sort considered a stable or unstable sorting algorithm?

Heap sort is generally considered unstable because it can change the relative order of equal elements during the heap building and sorting process.

What data structure does Heap sort use to organize elements?

A Linked List

B Heap

C Queue

D Stack

Heap sort uses a heap, a special tree-based structure, to organize elements for sorting.

Which heap type is used in Heap sort to sort elements in ascending order?

A Min-heap

B Binary Search Tree

C Max-heap

D Trie

Heap sort uses a max-heap to keep the largest element at the root for sorting in ascending order.

What is the worst-case time complexity of Heap sort?

A O(n log n)

B O(log n)

C O(n^2)

D O(n)

Heap sort always runs in O(n log n) time, even in the worst case.

Is Heap sort a stable sorting algorithm?

A Yes, always stable

B Stable only for small data

C Depends on implementation

D No, generally unstable

Heap sort is generally unstable because it can change the order of equal elements.

Which of these is a key advantage of Heap sort over Quick sort?

A Uses less memory and is in-place

B Always faster

C Easier to implement

D Stable sorting

Heap sort is in-place and uses less extra memory compared to Quick sort, which can use more stack space.

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

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

Compare Heap sort with Quick sort in terms of time complexity, memory use, and stability.

Focus on differences in performance and behavior.