1. In what time can a binary heap be built?
a) O(N)
b) O(N log N)
c) O(log N)
d) O(N2)
Explanation: The basic strategy is to build a binary heap of N elements which takes O(N) time.
2. Heap sort is faster than Shell sort.
a) true
b) false
Explanation: Heap sort is slower than Shell sort because Shell sort uses Sedgewick’s increment sequence.
3. In what position does the array for heap sort contains data?
a) 0
b) 1
c) -1
d) anywhere in the array
Explanation: The array for heap sort contains data at position 0 whereas for a binary heap, array begins at 1. This is the reason for its complexity.
4. In heap sort, after deleting the last minimum element, the array will contain elements in?
a) increasing sorting order
b) decreasing sorting order
c) tree inorder
d) tree preorder
Explanation: By logic, after deleting minimum element, the heap will contain elements in decreasing sorting order. We can change this by altering the ordering property.
5. What is the typical running time of a heap sort algorithm?
a) O(N)
b) O(N log N)
c) O(log N)
d) O(N2)
Explanation: The total running time of a heap sort algorithm is mathematically found to be O(N log N).
6. How many arrays are required to perform deletion operation in a heap?
a) 1
b) 2
c) 3
d) 4
Explanation: To perform deletion operation in a heap, we require 2 arrays and that occupies extra memory space and hence increase in running time.
7. What is the time taken to perform a delete min operation?
a) O(N)
b) O(N log N)
c) O(log N)
d) O(N2)
Explanation: The time taken to perform a deletion of a minimum element is mathematically found to be O( log N).
8. Heap sort is an extremely stable algorithm.
a) true
b) false
Explanation: Heap sort uses fewer comparisons than other sorting algorithms and hence it is an extremely stable algorithm.
9. What is the average number of comparisons used in a heap sort algorithm?
a) N log N-O(N)
b) O(N log N)-O(N)
c) O(N log N)-1
d) 2N log N + O(N)
Explanation: The average number of comparisons in a heapsort algorithm is mathematically found to be 2N log N + O(N).
10. What is the time taken to copy elements to and from two arrays created for deletion?
a) O(N)
b) O(N log N)
c) O(log N)
d) O(N2)
Explanation: The time taken to copy elements to and from the main array and extra array is found to be O(N).
Design and Analysis of Algorithms
Heap What?
First things first, what on earth is a heap? No, it's not a pile of dirty laundry. In algorithm-speak, a heap is a specialized tree-based data structure where the parent node is always greater (for max heap) or smaller (for min heap) than its children. It's like a family tree, but with a strict pecking order.
Sorting Magic
Heapsort is our algorithmic wizardry that takes advantage of this heap structure. Picture it as a sorting hat, but for numbers. It works by creating a max heap (or min heap), and then repeatedly swapping the root (the maximum or minimum value) with the last element of the heap. This nifty trick organizes the array into sorted segments, just like organizing your bookshelf by genre.
The Quirks and Charms
What makes Heapsort so spellbinding? Well, it's not just about sorting. Unlike some sorting spells that take up loads of memory, Heapsort is an in-place algorithm. It sorts the array right where it sits, saving memory like a true minimalist wizard.
And get this – Heapsort has a guaranteed worst-case time complexity of O(n log n). That's like saying, "I promise I'll find my keys in a reasonable amount of time." It's reliable and efficient, making it a go-to choice for those who want their algorithms to be as dependable as a trusty sidekick.