1. Heap and Heapsort. (a) Run Build-Heap on the array [10,9,4,7,6, 2, 3, 1, 8, 5] to construct a min heap. Write down the resulting array. Then, run the loop in Heapsort for three iterations. For each iteration write down the array after Heapify-Down is finished. You do not need to show intermediate steps. (b) Show that the leaves of a heap occupy the positions [],...,n- 1 of the array. (c) In the procedure Build-Heap, why do we decrease i from [2]-1 to 0 instead of increasing from 0 to []-1? Give an example array where increasing i fails to create a valid min heap.

1. Heap and Heapsort. (a) Run Build-Heap on the array [10,9,4,7,6, 2, 3, 1, 8, 5] to construct a min heap. Write down the resulting array. Then, run the loop in Heapsort for three iterations. For each iteration write down the array after Heapify-Down is finished. You do not need to show intermediate steps. (b) Show that the leaves of a heap occupy the positions [],...,n- 1 of the array. (c) In the procedure Build-Heap, why do we decrease i from [2]-1 to 0 instead of increasing from 0 to []-1? Give an example array where increasing i fails to create a valid min heap.

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: 48. If the list through the heap is doubly-linked, it is easy to find the node to set "las to...…

A: The answer has given below:

Q: a) Creat a MIX HEAP illustration for the array values of (six, three, twelve, nine, twenty-five,…

Q: void build (int[] elts, int N); // The "magic" build operation which constructs a heap in O(N) time…

A: the code is an given below public class JavaMinHeap { private final int[] HeapArray; private…

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: 2. Bottom-Up Min-Heapify: For the following numbers, what is the resulting (1-indexed) heap after…

A: ->A heap is a binary tree with all levels filled except, the last. The last level is filled in…

Q: Create a data type that allows you to insert, delete the maximum, and delete the minimum (all in…

A: A heap is a data structure that allows you to discover the maximum and minimum element in constant…

Q: Assume you have the max-heap 100, 80, 70, 60, 50, 40, 30, 50, 10, 20. What is the final state of the…

A: A heap is a complete binary tree, and a binary tree is a tree where a node can have at most two…

Q: Trace out the heap sort algorithm for the following list: {25, 44, 55, 99, 30, 37, 15, 10, 2, 4}.

A: Given Trace out the heap sort algorithm for the following list: {25, 44, 55, 99, 30, 37, 15, 10, 2,…

Q: Let us heap sort the list L ={D, B, G, E, A, H, C, F} made use of in Example 17.16. The first phase…

A: A comparison-based ordering method based on the Binary Heap data structure is called heap sort. It…

Q: You have to draw the heap; you can not show it as an array or vector. Data Elements: 22 5 16 4 8 51…

A: HEAP SORT I)Heap sort is a sorting technique for the contrast based on the data structure of Binary…

Q: Give the array that results immediately after completing the first phase of heapsort (heap…

A: Answer is

Q: first parameter is an array that contains all the elements that // will go into the heap; the second…

A: the code is an given below public class JavaMinHeap { private final int[] HeapArray; private…

Q: Bottom-Up Min-Heapify the following numbers, what is the resulting (1-indexed) heap after…

Q: ap sort is the process of two steps: 1. Transform or creating or rebuilding the given array into a…

A: Heap sort is an efficient comparison-based sorting algorithm that operates in two main stages:…

Q: 1. Generate an Array A of 10^7 random numbers. Make its copies B and C. Sort A using Merge Sort, B…

A: #include <iostream> using namespace std; void heapify(int arr[], int n, int i) { //…

Q: 3. Sort the array A= [10, 15, 11, 12, 6, 28, 19] by using the operation (insertion and deletion) of…

A: This code will run without comment: #include <iostream> using namespace std; void…

Q: There is an algorithm for making the heap complete: 1. Remove the node at the root. 2. Move the node…

A: The data is continuously deleted from the heap in sorted order when this approach is used. The code…

Q: This question is on heapsort. (a) We aim to construct a max heap based on an array A. When we call…

A: maxHeapify(array, size, k) set k as largest leftChild = 2k + 1 rightChild = 2k + 2 if…

Q: What is the difference between stack and heap memory?

A: Difference between heap memory and Stack Memory: Stack memory allocation takes place on contiguous…

Q: Build a heap from the following array. Show the heap after ???????() occurred at each node. ? = [3,…

A: given array [3, 5, 1, 6, 2, 0, 8, 11, 9]

Question

1.
Heap and Heapsort.
(a) Run Build-Heap on the array [10, 9,4,7,6,2,3,1, 8,5] to construct a min heap. Write down the resulting
array. Then, run the loop in Heapsort for three iterations. For each iteration write down the array after
Heapify-Down is finished. You do not need to show intermediate steps.
(b) Show that the leaves of a heap occupy the positions [],...,n-1 of the array.
(c) In the procedure Build-Heap, why do we decrease i from [2]-1 to 0 instead of increasing from 0 to
[2]-1? Give an example array where increasing i fails to create a valid min heap.

Expert Solution

This question has been solved!

Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.

This is a popular solution!

SEE SOLUTION Check out a sample Q&A here

Step 1: Heap and Heapsort

VIEW

Step 2: (a) Building a Min Heap:

VIEW

Step 3: (b) heap occupy the positions [n/2], ..., n-1 of the array

VIEW

Step 4: (c) Build-Heap procedure

VIEW

Solution

VIEW

Trending now

This is a popular solution!

Step by step

Solved in 5 steps

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

Please don't copy the solution. Assignment: For this week’s assignment, you’re going to be creating a Heap Sorter. It should be able to take input (using CIN), place it into proper Max Heap form in an array, and once it’s done accepting input, put the array in order using a Heap Sort. For the sake of simplicity, our heap trees will be made of an array that’s only seven elements long. Make sure to define your arrays ahead of time with garbage filler data before you start putting in your CIN data. Remember to use the binary heap traversal trick when dealing with your array-based tree. Please sort the following lists of inputs: 1.) 12, 40, 2, 6, 88, 90, 5 2.) 1, 2, 3, 4, 5, 6, 7 3.) 7, 6, 5, 4, 3, 2, 1 4.) 42, 64, 355, 113, 101, 13, 35 5.) 12, -5, 24, -4, 48, -3, 96
2.) C [10] = {5, 1,2,8,6,10,3,9,4,7} heap size = 10 Do Heapify (C, 1). What the values in the array C starting from the index 0 to 9?
Push 13 to the following min-heap and write the resulting heap array in the answer space. Write the array like a normal C++ array (e.g.: {67, 54, 123, ...}). 54 51 62 27 59 12pt ✓ Paragraph 28 ⠀ 50 Edit View Insert Format Tools Table 3 44 22 24
You're given an array A[1...7] Heap-Insert(A, 8), what is the resulting A? (9, 7, 6, 4, 1, 5, 3). If you execute Max-
4. Build a Max-Heap on the following array A= Show all the steps.
Show the array and heap after each step: 1. Add the following: 9 18 37 6 5 2 10 4 2. Remove the following: 10, 6
(b) Now consider storing a heap as a linked list with pointers. Give pseudo-code on how you would store a heap node, and which modifications you need to make to the heap routines that we discussed in class. What are the runtimes of the heap routines?
char ** doubleIt (char **arr, int *maxsize); The doubleIt function will increase the heap size by doubling the original space. The functions takes 2 arguments: 1. A double pointer of type char called arr. This is a 2D dynamic array that contains words (strings) from the respective category (noun, verb, adjective, preposition). This is the original heap. 2. A pointer of type int called maxsize. This pointer holds the address of an integer that keeps track of the maximum amount of strings the 2D dynamic array can store. When this function is invoked, the current size of the dynamic array is at capacity so the values should match. This value will need to be multiplied by 2. The function allocates a new heap that is twice the size of the original heap and copy the values from the original heap into the new heap. One important note about this is that you have to properly copy the values over in order to avoid segmentation fault. Think about how this can be avoided. That is part of the…
Suppose you want to use Heapsort to sort the contents of the following array in alphabetical order: [C; A; G; B; D; F; E]. Show the array's contents after the heapBuild method has been performed, i.e. when the array represents a heap
java