in C++
In this assignment you will implement a heap data structure that is
able to do Heapsort. Implement it in
an array.
The first line of input will be given in the form of a list of
numbers to insert into a binary tree in level
order. Assume it is a complete tree. When finished inserting
heapify the tree into a MAXHEAP. Print
out the level order traversal for it.
Then remove the head (min) and print it out one at a time in order
to print the list sorted.
Notes:
-Comment your source code appropriately.
-Test your program by running with different input to make sure the
output is correct.
Test and execute your program by using data-in by Linux input
redirection. If your executable code is
Ast# and your data file is named data# execute as: Ast# <
data#
Sample Input:
198 543 766 745 62 562 805 654 52 936 207 251 495 701 303 823 460
663
21 314 434 543 465 100 597 567 752 624 565 778 529
Sample output:
Heapify Complete:
936 823 805 745 752 778 654 663 434 543 597 567 701 766 195 460 52
21
314 62 207 465 100 251 562 495 624 565 303 529
Sorted List:
21 52 62 100 198 207 251 303 314 434 460 465 495 529 543 543 562
565
567 597 624 654 663 701 745 752 766 778 805 823 936
Part II:
-What is the time complexity for the Heapify algorithm? How about
for the sorting? Insert? How could
you improve this?
#include <iostream>
#include <conio.h>
using namespace std;
void max_heapify(int *a, int i, int n)
{
int j, temp;
temp = a[i];
j = 2 * i;
while (j <= n)
{
if (j < n && a[j+1] > a[j])
j = j + 1;
if (temp > a[j])
break;
else if (temp <= a[j])
{
a[j / 2] = a[j];
j = 2 * j;
}
}
a[j/2] = temp;
return;
}
void build_maxheap(int *a,int n)
{
int i;
for(i = n/2; i >= 1; i--)
{
max_heapify(a,i,n);
}
}
void heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2*i + 1; // left = 2*i + 1
int r = 2*i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i)
{
swap(arr[i], arr[largest]);
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
// main function to do heap sort
void heapSort(int arr[], int n)
{
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// One by one extract an element from heap
for (int i=n-1; i>=0; i--)
{
// Move current root to end
swap(arr[0], arr[i]);
// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
/* A utility function to print array of size n */
void printArray(int arr[], int n)
{
for (int i=0; i<n; ++i)
cout << arr[i] << " ";
cout << "\n";
}
int main()
{
int n, i, x;
cout<<"enter no of elements of array\n";
cin>>n;
int a[20];
cout<<"enter" <<n<<" element: ";
for (i = 1; i <= n; i++)
{
cin>>a[i];
}
build_maxheap(a,n);
cout<<"Heapify complete:\n";
for (i = 1; i <= n; i++)
{
cout<<a[i]<<" ";
}
heapSort(arr, n);
cout << "Sorted list: \n";
printArray(arr, n);
getch();
}
Time Complexity of a heapify algorithm
Consider the following algorithm for building a Heap of an input array A.
BUILD-HEAP(A) heapsize := size(A); for i := floor(heapsize/2) downto 1 do HEAPIFY(A, i); end for END
A quick look over the above algorithm suggests that the running
time is , since each call to
Heapify costs and Build-Heap
makes such calls.
This upper bound, though correct, is not asymptotically tight.
We can derive a tighter bound by observing that the running time
of Heapify depends on the height of the tree ‘h’
(which is equal to lg(n), where n is number of nodes) and the
heights of most sub-trees are small.
The height ’h’ increases as we move upwards along the tree. Line-3
of Build-Heap runs a loop from the index of the
last internal node (heapsize/2) with height=1, to the index of
root(1) with height = lg(n). Hence, Heapify takes
different time for each node, which is .
For finding the Time Complexity of building a heap, we must know
the number of nodes having height h.
For this we use the fact that, A heap of size n has at most
nodes with height h.
Now to derive the time complexity, we express the total cost of Build-Heap as-
(1)
Step 2 uses the properties of the Big-Oh notation to ignore the ceiling function and the constant 2(). Similarly in Step three, the upper limit of the summation can be increased to infinity since we are using Big-Oh notation.
Sum of infinite G.P. (x < 1)
(2)
On differentiating both sides and multiplying by x, we get
(3)
Putting the result obtained in (3) back in our derivation (1), we get
(4)
Hence Proved that the Time complexity for Building a Binary Heap is .
In C++ In this assignment you will implement a heap data structure that is able to do Heapsort. ...
need help to complete this java program // add appropriate import statements here. // These imports you can leave as is. import javafx.application.Application; import javafx.scene.Group; import javafx.scene.Scene; import javafx.scene.canvas.Canvas; import javafx.scene.canvas.GraphicsContext; import javafx.scene.paint.Color; import javafx.stage.Stage; /** @author yourAccountNameHere */ public class ConnectTheDots extends Application { /* * Do not add code to main(). Add it below in connectTheDots instead. */ public static void main(String[] args) { launch(args); } /*...
In C++ Programming: Using a single for loop, output the even numbers between 2 and 1004 (inclusive) that iterates (loops) exactly 502 times. The outputted numbers be aligned in a table with 10 numbers per row. Each column in the table should be 5 characters wide. Do not nest a loop inside of another loop. Hint: First create and test the code that output the numbers all on one line (the command line will automatically wrap the output to new...
Create a program that will use the attached input file and perform the following operations. Read the file into an appropriate JCF data structure. Look up a (list of) names and numbers matching a last name or the first letters of a last name, ignoring case. Look up a (list of) names and numbers matching a number or the first digits of a number. Add a name and number to the list. Sort the list by first name, last name...