Suppose we want to use the Heapsort algorithm to sort a large list of numbers. Our first step is to convert the input list to a heap, and then run BUILD-MAX-HEAP, which applies MAX-HEAPIFY on all the nodes in the heap, starting at the bottom and moving towards the top. (Think about why we do it bottom-up instead of top-down.) An example is provided on pg. 157 of the textbook. In this example, A = [4,1,3,2,16,9,10,14,8,7]. The end result of BUILD- MAX-HEAP is [16,14,10,8,7,9,3,2,4,1]. I strongly encourage you to go through this example, step by step. A total of 7 swaps are made by BUILD-MAX-HEAP. You can check that the seven swaps occur in this order: (14,2), (10,3), (16,1), (7,1), (16,4), (14,4), (8,4). Here is another way to see this: 2 goes down one level, 3 goes down one level, 1 goes down two levels, and 4 goes down three levels. Adding the underlined numbers, we see that the total number of swaps is 1+1+2+3 = 7. %3D Suppose A = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]. Determine BUILD-MAX-HEAP(A), and also determine the total number of swaps.

Suppose we want to use the Heapsort algorithm to sort a large list of numbers. Our first step is to convert the input list to a heap, and then run BUILD-MAX-HEAP, which applies MAX-HEAPIFY on all the nodes in the heap, starting at the bottom and moving towards the top. (Think about why we do it bottom-up instead of top-down.) An example is provided on pg. 157 of the textbook. In this example, A = [4,1,3,2,16,9,10,14,8,7]. The end result of BUILD- MAX-HEAP is [16,14,10,8,7,9,3,2,4,1]. I strongly encourage you to go through this example, step by step. A total of 7 swaps are made by BUILD-MAX-HEAP. You can check that the seven swaps occur in this order: (14,2), (10,3), (16,1), (7,1), (16,4), (14,4), (8,4). Here is another way to see this: 2 goes down one level, 3 goes down one level, 1 goes down two levels, and 4 goes down three levels. Adding the underlined numbers, we see that the total number of swaps is 1+1+2+3 = 7. %3D Suppose A = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]. Determine BUILD-MAX-HEAP(A), and also determine the total number of swaps.

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

Create a HeapVector that is more effective and only maintains the order of its values when necessary. Values are added by appending them to the heap's end and setting the nonHeap flag to true. The nonHeap flag is examined when values are removed, and the Vector is heapified if necessary. What are the add and delete operations' worst-case and best-case running times?
use python language for code plz do within 10 min please .thanks in advance
There is one stacks and one queue q and then following operations are performed upon these two. Push A, enqueue B, push C, pop, pop, enqueue D, push E, dequeue, enqueue F .What is the total number of elements, which are left in the queue and stack in the end.
Implement a simple linked list in Python (Write source code and show output) with basic linked list operations like: (a) create a sequence of nodes and construct a linear linked list. (b) insert a new node in the linked list. (b) delete a particular node in the linked list. (c) modify the linear linked list into a circular linked list. Use this template: class Node:def __init__(self, val=None):self.val = valself.next = Noneclass LinkedList:"""TODO: Remove the "pass" statements and implement each methodAdd any methods if necessaryDON'T use a builtin list to keep all your nodes."""def __init__(self):self.head = None # The head of your list, don't change its name. It shouldbe "None" when the list is empty.def append(self, num): # append num to the tail of the listpassdef insert(self, index, num): # insert num into the given indexpassdef delete(self, index): # remove the node at the given index and return the deleted value as an integerpassdef circularize(self): # Make your list circular.…
Only 2
1. Write a Java Program to arrange the following names in Ascending order using Heap Sort algorithm . YourNames.add("Amal");YourNames.add("Huda");YourNames.add("Seham");YourNames.add("Yusra");YourNames.add("Mohammed ");YourNames.add("Khadija");YourNames.add("Ruqaya");YourNames.add("Tif");YourNames.add("Alaa");YourNames.add("Atheer");
What is the benefit of having a link-based implementation of the List that also tracks a reference to the last Node in the chain? Select one: a. It requires more pointes to be adjusted when performing the basic List operations b. It makes adding a new entry to a specified position an O(1) operation c. It makes the remove operation an O(1) operation d. It makes adding a new entry to the back of the List an O(1) operation
Write an algorithm for the following problem in java: Find the numbers that are greater than the number d between n and m node values in the linked list Write a java code that implementing the algorithm? What is the time complexity of your code?
Execute a program that will split a circularly linked list P with n nodes intotwo circularly linked lists P1, P2 with the first n/2 and the last n – n/2 nodes ofthe list P in them.
Reverse a singly linked list by changing the pointers of the nodes. The datarepresented by the list should continue to remain in the same nodes of the originallist.For example, given a singly linked list START, as shown in Figure P6.9(a), the listneeds to be reversed, as shown in Figure P6.9(b), by manipulating the links alone.
Write a program for Stack (Array-based or linked list-based) in Python. Test the scenario below with the implementation and with the reasoning of the answer. Make comments with a short description of what is implemented. Include source codes and screen-captured outputs. Stack: A letter means doing a push operation and an asterisk means doing a pop operation in the below sequence. Give the sequence of letters that are returned by the pop operations when this sequence of operations is performed on an initially empty stack. A*BCE**F*GH***I*
A singly linked list can be reversed by altering the nodes' pointers. The original list's nodes should still contain the data that the list represents.For instance, if a single linked list START is supplied, as in Figure P6.9(a), the list must be reversed using just the links, as in Figure P6.9(b).