CMPSC 465
Data Structures & Algorithms
Spring 2024
Worksheet 3
1. Heapsort. Please consider the following array, which represents a min heap.
A = [1, 2, 9, 5, 6, 10].
Suppose we remove the element at position 0 of the heap. How does the resulting heap look? Write both the array and tree representation of the heap.
2. Heaps Operations. Suppose we run Build-Heap on the array A = [5, 3, 17, 10, 84, 19, 6, 22, 9]. What is the resulting min heap?
3. Heaps Operations. Show that a heap with n elements has height ⌊log n⌋ .
4. Creating heaps. We can build a heap by repeatedly inserting the elements into the heap. Would this always create the same heap as Build-Heap when run on the same input array? Prove that they do, or provide a counterexample.
5. Find k-th smallest. Given an array of n elements and an integer k ≥ 0 we would like to find the k-th smallest element in the array.
1. Provide an algorithm for this problem that uses a min heap with running O(n+klog n).
2. Provide an algorithm for this problem that uses a max heap with running O(nlog k).
3. Which algorithm has better running time?