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

Related questions

Q: 1. In an array-based heap, what array index do we put a new entry into in the first step of the add…

A: Given:

Q: The following is a max-heap. After inserting a new node with key equal to 88, what will the array…

Q: For starting array 25 22 24 28 26 29 21 23 27, tell, for each element: what is the FIRST other…

A: A heap is a specialized data structure that is a complete binary tree (a tree structure in which…

Q: Assume you are using a backtracking algorithm to search for the node 40 in the max heap represented…

Q: Suppose a priority queue is implemented as a binary search tree of integers. Draw the tree resulting…

A: A priority queue is an abstract data-type similar to a regular queue or stack data structure in…

Q: Assuming that the array shown below represents a binary tree of nodes holding Integer objects,…

A: A required tree will be: shown below:-

Q: Assume we have k heaps, each with a maximum of n items. These are to be combined into a single heap.…

A: Given: We build a new linked list, L, that is empty. We continually remove the highest priority…

Q: Insert the following n objects, in the order given, into a binary min-heap and place your answer…

A: A tree is a hierarchical data structure used in computer science that is made up of nodes connected…

Q: The following array is already a Heap. Illustrate how HeapSort works on this Heap. You only have to…

Q: Perform a depth-first traversal (DFT) on the digraph below starting at vertex A.Complete the table…

A: We need to fill in the table with the order of visiting nodes and the state of the stack at each…

Question

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
%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(1)
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)
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).

Expert Solution

Step 1

Trending now

This is a popular solution!

Step by step

Solved in 2 steps with 2 images

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

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?