1. Heap-sort (1+4 points) a. The array int Data[k] shown below contains a heap. (i) Draw a diagram of the initial heap tree. At each node, show the values of both the index k and its content Data[k]. Initial given heap: Index k: 0 1 2 3 4 5 6 7 8 Data[k] 60 55 50 35 40 25 45 20 30 (ii) Draw a diagram of the heap tree and the array contents of Datata[k] after the first and after the second highest maximums are deleted one by one from the initial heap in the heap-sort algorithm. You can briefly describe your solution with diagrams on how you got the answers. Template for the Answers: Heap after the first maximum (60) is removed and placed at the end: DIAGRAM 1 Index 0 1 2 3 Data: 45678 Heap after the second maximum (55) is removed and placed near the end (before 60): DIAGRAM 2 Index 0 0 1 2 3 4 5 6 7 8 Data:

1. Heap-sort (1+4 points) a. The array int Data[k] shown below contains a heap. (i) Draw a diagram of the initial heap tree. At each node, show the values of both the index k and its content Data[k]. Initial given heap: Index k: 0 1 2 3 4 5 6 7 8 Data[k] 60 55 50 35 40 25 45 20 30 (ii) Draw a diagram of the heap tree and the array contents of Datata[k] after the first and after the second highest maximums are deleted one by one from the initial heap in the heap-sort algorithm. You can briefly describe your solution with diagrams on how you got the answers. Template for the Answers: Heap after the first maximum (60) is removed and placed at the end: DIAGRAM 1 Index 0 1 2 3 Data: 45678 Heap after the second maximum (55) is removed and placed near the end (before 60): DIAGRAM 2 Index 0 0 1 2 3 4 5 6 7 8 Data:

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

48. If the list through the heap is doubly-linked, it is easy to find the node to set "las" to... True False
Array of tree : [25, 33, 35, 18, 22, 29, 55, 3, 1, 98] Change the tree into a max heap by showing how the contents of the array change step by step. Add a comment to explain what you are doing in each step.
Programming language: JAVA Show the heap-based(min) priority queue constructed by inserting the following elements, either graphically or by listing the contents of the underlying array 8 6 0 4 2 1 3 5 7 9
*Please using JAVA only* Objective Program 3: Binary Search Tree Program The primary objective of this program is to learn to implement binary search trees and to combine their functionalities with linked lists. Program Description In a multiplayer game, players' avatars are placed in a large game scene, and each avatar has its information in the game. Write a program to manage players' information in a multiplayer game using a Binary Search (BS) tree for a multiplayer game. A node in the BS tree represents each player. Each player should have an ID number, avatar name, and stamina level. The players will be arranged in the BS tree based on their ID numbers. If there is only one player in the game scene, it is represented by one node (root) in the tree. Once another player enters the game scene, a new node will be created and inserted in the BS tree based on the player ID number. Players during the gameplay will receive hits that reduce their stamina. If the players lose…
4. Assume X = {3,4,6,9,8,7,16,15,20,19} is an array representation of a binary heap, such that each element in X represents a node on the heap. Delete one node from the heap. After the deletion, the root node of the tree representing the heap is node The left child of the root node is node and the right child of the root node is node . The right child of node 8 is node A Que
3. Draw the binary heap in its tree form from its array form: 0 1 2 3 4 5 6 7 8 9 10 11 12 2 3 4 9 10 17 15 11 9 13 22 20
1. Given the unsorted array write the pseudo code so sort it and find a specific element x a. Find (array, x) //first sort the array //search for element x using binary search 2. Given the following stack A = { 29,18,10,15,20,9,5,13,2,4,15} Create a queue by taking the elements from the top of the stack and adding them to a queue 3. what are the worst-case, average-case, and best-case complexities of insertion-sort, merge-sort, and quiksort 4. Given the following array A = {3,13,89,34,21,44,99,56,9} Illustrate the execution of the sorting algorithms on the given array: * Merge-sort algorithm * Quicksort (using the median-of-three pivot) algorithms * Selection Sort algorithm For each fundamental iteration or recursion of the algorithm, write the content of the array. 5. Evaluate the following postfix expression made using a stack: 234*5*-
DATA STRUCTURES AND ALGORITHMS C++ Build a heap tree from the given information or values. Write an algorithm that ‘SORT’ the data maintained in heap such that when data is retrieved from the heap, it should be sorted in descending order. Also show its step by step working. 50 45 65 60 75 90 15 35 70 45 55
Exercise #2 Draw the binary tree that has the following preorder and inorder and postorder traversals. Inorder sequence: D, B, E, A, F, C, G Preorder sequence: A, B, D, E, C, F, G Postorder sequence: D, E, B, F, G, C, A Exercise #3 сл Add 12 to the following max heap
List-Based Heap Implementations: The book starts out by discussing the concept of a priority queue and how to implement it conceptually. Then, the first implementation is presented: using an array or Python sequence to represent the heap. Data Storage: The book stores elements of a priority queue within a custom object (an _Item) which wraps and provides almost no support for the stored data. For this section, you will be storing your key and value as an ordered pair (or tuple) of two values where the first element is the key and the second element is the value. 1. What are the inherent benefits and drawbacks of this (array-based) backing representation? Discuss with respect to implementation, efficiency, and memory usage. (PI 1.2/ABET[1], PI 6.1/ABET[6])
Heap Operation 1. pq.Enqueue(28); 2. pq.Enqueue(2); 3. pq.Enqueue(40); 4. pq.Dequeue(x); 5. pq.Dequeue(y); 6. pq.Dequeue(z); 56 27 42 26 15 3 19 Values x, y, z? 25 24
C++ DATA STRCUTURES AND ALGORITHMS Build a heap tree from the given information or values. 50 45 65 60 75 90 15 35 70 45 55