QUESTION

4/16/12 Courses/CS 50×2/Assignments/(DS) Binary Min Heap – ASU Computer Science Wiki

Courses/CS 50×2/Assignments/(DS) Binary Min Heap

From ASU Computer Science Wiki

< Courses | CS 50×2 | Assignments

Binary Heap

A Binary Heap is basically a binary tree in which the following conditions hold:

In a Min-Heap , the smallest item is always at the root:

For any node n, n may have at most 2 children, whose values must be greater than (or equal to) the

value at n.

For a Max-Heap , the concept is the same, except that the largest item is always at the root, and the values at

the children are always less than (or equal to) the value at the parent.

In this assignment, you will be building a binary min-heap of integer values. Heaps commonly use arrays

internally to perform the actual storage, but to make this heap more dynamic—while maintaining the

advantages of the array—you will be using the Standard Template Library vector as internal storage. Your

class IntMinHeap should provide the following interface:

class IntMinHeap{

private:

vector<int> container;

public:

class Empty_Heap_Exception{};

void insert(int item);

int remove();

void print_structure(unsigned subroot_index = 0, unsigned level = 0);

unsigned size(){ return container.size(); }

};

Place the prototype in a file called heap.h and definitions of the methods in a file called heap.cpp. A

description of the class follows:

private members

container: the vector used to actually store values from the heap.

public interface

class Empty_Heap_Exception: a placeholder class used when an attempt is made to remove

a value from an empty heap.

insert: a method used to insert an integer into the heap. It should add the value at the end of

the vector, then “percolate up” to restore the min-heap property.

remove: a method used to remove and return the integer value at the root of the heap (the

smallest value in the heap). You should replace the root’ s value (after storing it in a variable)

with the value of the last element in the vector; then “sift down” the value by recursively

swapping it with the value of the smallest of its children until the min-heap property is restored. If

the heap is empty, this method should throw an instance of Empty_Heap_Exception.

print_structure: a method that will recursively print the heap “sideways” (see below) so that

you can verify the correctness of your code more easily.

You may add other methods, but the ones shown above must be provided, and must match the specification

given here exactly.

You will find the information at http://www.cplusplus.com/reference/stl/vector/ useful for learning to the

Standard Template Library class vector. One hint is that the vector will take care of resizing itself

1/2https://wiki.cs.astate.edu/index.php?title=Courses/CS_50x2/Assignments/(DS)_Binary_Min_Heap&m…

4/16/12 Courses/CS 50×2/Assignments/(DS) Binary Min Heap – ASU Computer Science Wiki

automatically as long as you always add and remove using the available methods, such as push_back() and

pop_back() (but to get the value before removing, you would also need to know the back() method). You

can also access the vector by index just like with a normal array, but you must be careful (as always) not to

access it out-of-bounds when doing so.

You should also create a testing file main.cpp in which you place code to fully test the IntMinHeap class.

Note that your main program will most likely be replaced during grading, so do not deviate from the required

interfaces for any of the required classes.

Example of “Sideways” tree output

Given the binary tree shown below: Note: the exampl e does not show a heap.

The output of the print_structure method would be:

11

10

7

5

3

2

Note: Using tabs to separate the levels will be sufficient for trees with small node values. Larger values might

require more output formatting… For this assignment, you can assume small values (no more than three

digits).

Create a .zip or .tar.gz (or similar) archive of all the source files in your project (NOT any binary files!) and

submit to the [CSCADE (http://cscade.cs.astate.edu) ] website.

Upload your solution in a file named heap.zip.

Retrieved from “https://wiki.cs.astate.edu/index.php/Courses/CS_50x2/Assignments/(DS)_Binary_Min_Heap”

This page was last modified on 13 April 2012, at 18:24.

2/2https://wiki.cs.astate.edu/index.php?title=Courses/CS_50x2/Assignments/(DS)_Binary_Min_Heap&m…

SOLUTION

**AVL Tree Program in C++**

#include<iostream.h>

#include<conio.h>

#include<stdio.h>

#include<stdlib.h>

struct node

{

int data;

node *left;

node *right;

};

node *tree=NULL;

node *insert(node *tree,int ele);

void preorder(node *tree);

void inorder(node *tree);

void postorder(node *tree);

int count=1;

void main()

{

clrscr();

int ch,ele;

do

{

clrscr();

cout<<“\n\t\aOUTPUT –>”;

cout<<“\n\t\a\a1—-INSERT A NODE IN A AVL TREE.\a\a”;

cout<<“\n\t\a\a2—-PRE-ORDER TRAVERSAL.\a\a”;

cout<<“\n\t\a\a3—-IN-ORDER TRAVERSAL.\a\a”;

cout<<“\n\t\a\a4—-POST-ORDER TRAVERSAL.\a\a”;

cout<<“\n\t\a\a5—-EXIT.\a\a\n”;

cout<<“\n\t\a\aENTER CHOICE::\a\a\n”;

cin>>ch;

switch(ch)

{

case 1:

cout<<“\n\t\a\aENTER THE ELEMENT::\a\a\n”;

cin>>ele;

tree=insert(tree,ele);

break;

case 2:

cout<<“\n\t\a\a****PRE-ORDER TRAVERSAL OF A TREE****\a\a\n”;

preorder(tree);

break;

case 3:

cout<<“\n\t\a\a****IN-ORDER TRAVERSAL OF A TREE****\a\a\n”;

inorder(tree);

break;

case 4:

cout<<“\n\t\a\a****POST-ORDER TRAVERSAL OF A TREE****\a\a\n”;

postorder(tree);

break;

case 5:

exit(0);

}

}while(ch!=5);

}

node *insert(node *tree,int ele)

{

if(tree==NULL)

{

tree=new node;

tree->left=tree->right=NULL;

tree->data=ele;

count++;

}

else

if(count%2==0)

tree->left=insert(tree->left,ele);

else

tree->right=insert(tree->right,ele);

return(tree);

}

void preorder(node *tree)

{

if(tree!=NULL)

{

cout<<tree->data;

printf(“\t”);

preorder(tree->left);

preorder(tree->right);

getch();

}

}

void inorder(node *tree)

{

if(tree!=NULL)

{

inorder(tree->left);

cout<<tree->data;

printf(“\t”);

inorder(tree->right);

getch();

}

}

void postorder(node *tree)

{

if(tree!=NULL)

{

postorder(tree->left);

postorder(tree->right);

cout<<tree->data;

printf(“\t”);

getch();

}

}

**Out Put:**

KA98

But you can order it from our service and receive complete high-quality custom paper. Our service offers Information technology essay sample that was written by professional writer. If you like one, you have an opportunity to buy a similar paper. Any of the academic papers will be written from scratch, according to all customers’ specifications, expectations and highest standards.”