In Heapsort, we assume that arrays are indexed from 1 to n. For example, if A = [16,4,10,14,7,9,3,2,8,1], then A[2] = 4 (highlighted in red). %3D The MAX-HEAPIFY(A, i) procedure inputs an array A and an index i. It assumes that the binary trees rooted at LEFT(i) and RIGHT(i) are max heaps, and ensures that A[i] "floats down" so that the output is an array that obeys the max-heap property. An example is provided on pg. 155 of the textbook. In this example, A = [16,4,10,14,7,9,3,2,8,1]. Then MAX-HEAPIFY(A, 2) %3D corrects the 2nd element of A, which is 4, moving this number to the correct position. The output is [16,14,10,8,7,9,3,2,4,1]. Let A = [2,11,10,9,6,7,8,3,5,4,1]. Determine MAX-HEAPIFY(A,1).

In Heapsort, we assume that arrays are indexed from 1 to n. For example, if A = [16,4,10,14,7,9,3,2,8,1], then A[2] = 4 (highlighted in red). %3D The MAX-HEAPIFY(A, i) procedure inputs an array A and an index i. It assumes that the binary trees rooted at LEFT(i) and RIGHT(i) are max heaps, and ensures that A[i] "floats down" so that the output is an array that obeys the max-heap property. An example is provided on pg. 155 of the textbook. In this example, A = [16,4,10,14,7,9,3,2,8,1]. Then MAX-HEAPIFY(A, 2) %3D corrects the 2nd element of A, which is 4, moving this number to the correct position. The output is [16,14,10,8,7,9,3,2,4,1]. Let A = [2,11,10,9,6,7,8,3,5,4,1]. Determine MAX-HEAPIFY(A,1).

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

The following is a max-heap. After extracting the node with maximum key, what will the array look like? Before extracting: 95 77 61 72 63 30 50 16 60 59 After extracting:
Splaysort. Splaysort is similar to heapsort and described in (VI.13 (p. 22). It is reportedly quite efficient in practice. In this question, we want to simulate this algorithm to sort the following input sequence of numbers: 89, 32, 11, 52, 46, 76, 29, 99, 23, 60, 42, 24. Begin by inserting each of these numbers into an initially empty splay tree, and then repeatedly deleteMin. Show the splay trees at the end of each operation.
Insert the following elements in sequence into an empty binary max heap: 1, 6, 4, 7, 2, 8, 9, 10 Draw the tree representation of the heap after every insertion.
Q.No.3 a) Which array out of A, B and C represents a 0 1 2 3 4 5 6 7 8 9 10 11 binary heap? Only one answer is right. A =|1 12 23 10 15 38 45 15 18 20 21 0 1 2 3 8 9 10 11 5 6. b) Write the heap out as a binary tree. B= 18 27 10 45 83 91 31 12 52 51 c) Add last 2 digit of your arid no(44). to the 0 1 2 3 4 5 6. 8 9 10 11 heap, making sure to restore the heap C=|1 13 20 21 65 54 67 41 30 83 52 invariant. How does the array look now?
Problem 6: Red black trees. Let D be a data structure on the set of positive integers,which supports the following operations:- Insert(D, x): insert x in D.- Remove(D, x): remove x from D.- Find(D, x): find x in D.- Count(D, x): returns the number of elements in D that are larger then x.We would like to implement D by using red black trees. Describe how can we modify a redblack tree such that all four operations have time complexity O(log n), where n denotes thenumber of elements in the structure. Elaborate why time complexity of all four operationsis O(log n).
you are given ten(10) numbers 9,5,4,5,7,3,2,9,10,1 Store these elements in a stack ADT in the order shown (i.e. start with 9 and end with 1). Pop elements from this stack and store the elements in a binary search tree. Traverse the binary search tree above and store the elements in a priority queue. Remove the elements from the priority queue in (iii) and construct a directed graph G such that (x,y) is an edge as long as x>y whenever x and y are vertices of G. Traverse the graph in (iv) using depth first search(DFS)
A. Consider the three given arrays (a), (b) and (c): 13 22 33 20 25 45 55 25 28 30 31 (a) 10 11 12 23 30 31 75 64 77 51 40 93 62 (b) 2 10 11 13 18 32 21 53 89 97 42 23 60 59 (c) 10 11 i) Which of the following arrays above represents a binary heap? Justify your choice. ii) Draw the heap as a binary tree. iii) Perform insert (29) operation to the heap. Show all your steps and show how the array looks like after the operation is done. iv) Perform removeMin operation on the heap. Show all your steps and show how the array looks like after the operation is done.
Python code please thank you!!
Q.No.3 Which array out of A, B and C represents a binary heap? Only one answer is right. Write the heap out as a binary tree. Add last 2 digit of your Roll no suppose your roll no is(47). to the heap, making sure to restore the heap invariant. How does the array look now?
Python code Screenshot and output is necessary
TheHeap = [10, 2, 7, 6, 5, 9, 12, 35, 22, 15, 1, 3, 4] is an array-based binary tree. Max stack Remove Max. Heap sort efficiency?