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.”
