Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

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?