int emptyLeaf = arr[currentSize];
what therefore doesn't point to an empty slot but to the last slot.
#include <iostream>
#include <fstream>
#include <string>
#include <iomanip>
using namespace std;
int binaryHeap[128]; // array to hold items in heap
int currentSize = 0; // variable to hold the size of array, also for getting last entry
int dataInput = 0; // variable used for adding to or removing from heap
static bool found = false;
static int temp = 0;
void deleteMin(int[], int = 0);
void insert(int[], int);
void print(int[]);
void readInput();
void showBinaryHeap(int,int);
void showBinaryHeap2(int,int);
void findSpecificItem(int[], int);
void percUp(int[], int);
void percDown();
void remove(int[], int);
int parent(int i) {return i/2;}
int left(int i) {return 2*i;}
int right(int i) {return 2*i+1;}
int main()
{
//cout << "\n\nThe number of items in the heap is: " << currentSize << "\n\n"; // a little formatting.
showBinaryHeap(1,0);
readInput();
print(binaryHeap);
// showBinaryHeap(1,0);
//deleteMin(binaryHeap, currentSize/2);
//cout << "\n\nThe number of items in the heap is: " << currentSize << "\n\n"; // a little formatting.
showBinaryHeap2(1,0);
//print(binaryHeap);
// showBinaryHeap(1,0);
// showBinaryHeap2(1,0);
cout << "Enter a number you would like to delete from the heap: ";
cin >> dataInput;
//findSpecificItem(binaryHeap, dataInput);
//percUp(binaryHeap, dataInput);
remove(binaryHeap, dataInput);
print(binaryHeap);
return 0;
}
/**print function. Takes in an array and prints it out**/
void print(int arr[])
{
cout << "\n";
for(int i = 1; i <= currentSize; i++) //will print until the LastEntry is hit
{
cout << arr[i] << "\t";
}
cout << "\n\nThe number of items in the heap is: " << currentSize << "\n\n"; // a little formatting.
}
/** showBinaryHeap prints the heap showing the proper structure
// Similar code and other notes for this function were found at
// http://www.d.umn.edu/~ddunham/cs4521s08/assignments/a4/assignment.html
// I couldn't figure out how to write this same function printing the structure properly (without rotation)....
// So unfortunately this function is not very robust at all..... :(
// Even so, I thought it would be neat to try and show the actual structure of the binary heap for this particular assignment anyway.
*/
void showBinaryHeap(int i, int depth) // i is the index of a subheap with given depth
{
if (i <= currentSize)
{
cout << setw(depth*6+20) << binaryHeap[i] << endl << endl; // height = 0
cout << setw(depth*6+12) << right(i) << setw(depth*6+16) << left(i) << endl << endl; // height = 1
cout << setw(depth*6+8) << left(right(i)) << setw(depth*6+8) << right(right(i)) << // height = 2
setw(depth*6+8) << right(left(i)) << setw(depth*6+8) << left(left(i)) << endl<< endl;
cout << setw(depth*6+6) << right(right(right(i))) << setw(depth*6+4) << left(right(right(i))) << // height = 3
setw(depth*6+4) << left(left(right(i))) << setw(depth*6+4) << right(left(left(i))) <<
setw(depth*6+4) << left(right(left(i))) << setw(depth*6+4) << right(right(left(i))) <<
setw(depth*6+4) << right(left(right(i))) << setw(depth*6+4) << left(left(left(i)))<< endl;
//showBinaryHeap(right(right(i)), depth);
//cout << setw(depth*6+6) << right(i+3);
//showBinaryHeap( right(i), depth+1 );
cout << endl << endl;
//showBinaryHeap( left(i), depth+1 );
}
}
/** BinaryHeap2 prints the heap showing the structure (on its side) using recursive calls
// Code and other notes for this function were found at
// http://www.d.umn.edu/~ddunham/cs4521s08/assignments/a4/assignment.html
// I couldn't figure out how to write this same function printing the structure properly (without rotation)....
*/
void showBinaryHeap2(int i, int depth) // i is the index of a subheap with given depth
{
if (i <= currentSize)
{
showBinaryHeap2( right(i), depth+1 );
cout << setw( depth*6 +4 ) << binaryHeap[i] << endl;
showBinaryHeap2( left(i), depth+1 );
}
}
void remove(int arr[], int specItem)
{
print(arr);
percUp(arr, specItem);
cout << "Heap with selected item at top: ";
print(arr); //print the heap with the changes
deleteMin(arr); //pop the value off the heap
cout <<"\nHeap after selected item is deleted: ";
print(arr); //print the heap again
showBinaryHeap(1,0);
}
void findSpecificItem(int arr[], int specItem)
{
//bool found = false; //flag for if the item is found in the heap
//int temp; //holds the address of the item to percolate up
for(int i = 1; i <= currentSize; i++) // loop to find the item in the heap
{
if(arr[i] == specItem) //if the array[index from the loop] is equal to the value
{
found = true; //sets the found flag to true
temp = i; //sets the temp to the index from the loop
}
}
if(found)
{
cout << "The item " << specItem << " was found!\n";
}
else //the item was not found in the for loop
{
cout << "Item was not found!" << endl; //tells you about it
}
}
void percUp(int arr[], int specItem)
{
//int temp = 0;
findSpecificItem(arr, specItem);
if(found) //if the value was found in the loop
{
while(temp != 1) //while the address of the item is not the top
{
swap(arr[temp], arr[temp/ 2]); //swap the item with its parent
temp = temp / 2; //reset the address so it still points to the right value
}
}
}
void percDown(){}
/**insert function fills heap with passed data**/
void insert(int arr[], int data)
{
int newLeaf = currentSize + 1; //sets the hole to the index after the last entry
int parent; //parent item used to store the index of the parent of the hole
//print(binaryHeap);
bool placed = false; // flag to see if data item is placed in the heap
if(currentSize == 0) // test to see if the heap is empty
{
arr[newLeaf] = data; // if the heap is empty the data item is placed in the hole
placed = true; // flag placed true skips while loop
}
while(placed == false) // while the data item is not placed in the heap
{
parent = newLeaf / 2; // set the parent of the newLeaf
//cout << "while" << endl << endl;
//print(binaryHeap);
if(binaryHeap[parent] < data) // check to see if the parent is < the data item
{
binaryHeap[newLeaf] = data;// the data is placed in the newLeaf
placed = true; // flag placed true ends while loop
//cout << "while if" << endl << endl;
//print(binaryHeap);
}
else // if the parent is !< the data
{
binaryHeap[newLeaf] = binaryHeap[parent]; // move the data from the parent down into the newLeaf
newLeaf = parent; // change the newLeaf to take the parents spot
//cout << "while else" << endl << endl;
//print(binaryHeap);
}
//heapify(newLeaf);
}
currentSize++; //increment the currentSize to adjust for newLeaf
}
/**deleteMin function removes the minimum element from the heap**/
void deleteMin(int arr[], int num)
{
//int i = 1;
int emptyLeaf = arr[currentSize];
int newLeaf = 1;
bool placed = false;
for(int i = 0; i <= num; i++)
{
while(!placed)
{
left(newLeaf);// = newLeaf * 2;
right(newLeaf);// = newLeaf * 2 + 1;
// if (left(newLeaf) < currentSize && right(newLeaf) < currentSize)
// {
if(left(newLeaf) > emptyLeaf && right(newLeaf) > emptyLeaf)
{
arr[newLeaf] = emptyLeaf;
placed = true;
}
else
{
if(arr[left(newLeaf)] < arr[right(newLeaf)])
{
arr[newLeaf] = arr[left(newLeaf)];
newLeaf = left(newLeaf);
}
else
{
arr[newLeaf] = arr[left(newLeaf)];
newLeaf = left(newLeaf);
}
}
// }
}
currentSize = --currentSize;
}
}
/**readInput function reads data from file and passes it to the heap by calling the insert function**/
void readInput()
{
//string input;
int input; // variable used for reading input from a file
ifstream infile("data.txt");
if(infile.is_open()) // if the data.txt file is open
{
while(!infile.eof()) // until the end of the file is reached
{
//getline(infile, input);
infile >> input; // read input from file one item at a time
// showBinaryHeap(1,0);
insert(binaryHeap, input); // insert each input item into the heap
print(binaryHeap);
// showBinaryHeap(1,0);
//cout << input << " ";
//cout << "\n\nThe number of items in the heap is: " << currentSize << "\n\n"; // a little formatting.
}
infile.close();
cout << endl << endl << endl;
}
else
{
cout << "Error reading file!" << endl;
exit(1);
}
}
swap(arr[temp], arr[currentSize]);
if(arr[temp] > arr[temp*2])
{
if(arr[temp*2] > arr[temp*2+1])
{
swap(arr[temp], arr[temp*2]);
}
}
else if(arr[temp] > arr[temp*2+1])
{
swap(arr[temp], arr[temp*2]);
}
--currentSize;
void remove(int arr[], int specItem)
{
findSpecificItem(arr, specItem);
if(found) //if the value was found in the loop
{
swap(arr[temp], arr[currentSize]);
showBinaryHeap2(1,0);
// while(arr[temp/2] == arr[temp]
if(arr[temp] < arr[temp/2]) // if the swapped value is less than it's parent
{ // then we will run through this loop (percUp) until heap property is satisfied
swap(arr[temp], arr[temp/2]); // swap the the value with it's parent
//temp = temp/2;
}
// Well this doesn't work....
// while(arr[temp] > arr[temp*2] || arr[temp] > arr[temp*2+1]); // run through this loop until heap property is satisfied (percDown)
{
if(arr[temp] > arr[temp*2]) // if the swapped value is greater than it's left child
{
if(arr[temp*2] > arr[temp*2+1]) // if left child is greater than the right child
{
swap(arr[temp], arr[temp*2]); // swap value with it's left child
temp = temp*2; // reset temp's value to stay accurate
}
}
else if(arr[temp] > arr[temp*2+1]) // if the swapped value is greater than it's right child
{
swap(arr[temp], arr[temp*2+1]); // swap value with it's right child
//temp = temp*2+1; // reset temp's value to stay accurate
}
}
//while(arr[temp] > arr[temp*2] || arr[temp] > arr[temp*2+1]); // run through this loop until heap property is satisfied (percDown)
--currentSize; // decrease the size of the heap
cout <<"\nHeap after selected item is deleted: ";
print(arr); //print the heap again
showBinaryHeap2(1,0);
}
}
// CIS 350 Project4
// Brian Acs
#include <iostream>
#include <fstream>
#include <string>
#include <iomanip>
using namespace std;
int binaryHeap[128]; // array to hold items in heap
int currentSize = 0; // variable to hold the size of array, also for getting last entry
int dataInput = 0; // variable used for adding to or removing from heap
static bool found = false;
static int temp = 0;
void deleteMin(int[], int = 0);
void insert(int[], int);
void print(int[]);
void readInput();
void showBinaryHeap(int,int);
void showBinaryHeap2(int,int);
void findSpecificItem(int[], int);
void remove(int[],int);
int parent(int i) {return i/2;}
int left(int i) {return 2*i;}
int right(int i) {return 2*i+1;}
int main()
{
readInput();
cout << "\nThe number of items in the heap is: " << currentSize << endl; // displays current total of items in heap
print(binaryHeap); // display the heap
cout << "\n\n\n"; //for display purposes
showBinaryHeap2(1,0); // display the heap showing structure (rotated 90 degrees)
deleteMin(binaryHeap, currentSize/2); // delete half of items from top of heap
print(binaryHeap); // display the heap
cout << "\n\n\n"; //for display purposes
showBinaryHeap2(1,0); // display the heap showing structure (rotated 90 degrees)
cout << "\nThe number of items in the heap is: " << currentSize << endl << endl; // displays current total of items in heap
cout << "Enter a number you would like to delete from the heap: "; // get user input on an item to delete
cin >> dataInput; // store user input into dataInput varaiable
remove(binaryHeap, dataInput); // remove the value that was stored in dataInput variable from the heap (if it is present)
print(binaryHeap); // display the heap
cout << "\n\n\n"; // for display purposes
showBinaryHeap2(1,0); // display the heap showing structure (rotated 90 degrees)
cout << "\nThe number of items in the heap is: " << currentSize << endl; // displays the current total of items in heap
return 0;
}
/**print function. Takes in an array and prints it out**/
void print(int arr[])
{
cout << "\n";
for(int i = 1; i <= currentSize; i++) //will print until the LastEntry is hit
{
cout << " " << arr[i] << " ";
}
cout << "\n";
}
/** showBinaryHeap prints the heap showing the proper structure
// Similar code and other notes for this function were found at
// http://www.d.umn.edu/~ddunham/cs4521s08/assignments/a4/assignment.html
// I couldn't figure out how to write this same function printing the structure properly (without rotation)....
// So unfortunately this function is not very robust at all..... :(
// Even so, I thought it would be neat to try and show the actual structure of the binary heap for this particular assignment anyway.
*/
void showBinaryHeap(int i, int depth) // i is the index of a subheap with given depth
{
i++;
if (i <= currentSize)
{
cout << setw(depth*6+20) << parent(i) << endl << endl; // height = 0
cout << setw(depth*6+12) << left(i) << setw(depth*6+16) << right(i) << endl << endl; // height = 1
cout << setw(depth*6+8) << left(right(i)) << setw(depth*6+8) << right(right(i)) << // height = 2
setw(depth*6+8) << right(left(i)) << setw(depth*6+8) << left(left(i)) << endl<< endl;
cout << setw(depth*6+6) << right(right(right(i))) << setw(depth*6+4) << left(right(right(i))) << // height = 3
setw(depth*6+4) << left(left(right(i))) << setw(depth*6+4) << right(left(left(i))) <<
setw(depth*6+4) << left(right(left(i))) << setw(depth*6+4) << right(right(left(i))) <<
setw(depth*6+4) << right(left(right(i))) << setw(depth*6+4) << left(left(left(i)))<< endl;
cout << endl;
}
}
/** BinaryHeap2 prints the heap showing the structure (on its side) using recursive calls
// Code and other notes for this function were found at
// http://www.d.umn.edu/~ddunham/cs4521s08/assignments/a4/assignment.html
// I couldn't figure out how to write this same function printing the structure properly (without rotation)....
*/
void showBinaryHeap2(int i, int depth) // i is the index of a subheap with given depth
{
if (i <= currentSize)
{
showBinaryHeap2( right(i), depth+1 );
cout << setw( depth*6 +4 ) << binaryHeap[i] << endl;
showBinaryHeap2( left(i), depth+1 );
cout << endl;
}
}
/**remove function removes the passed value that's in the heap if it's in the heap
more in depth - if the value is in the heap then this function swaps the node
holding that value with the node in the last position then sifts or percolates
up or down depending on what is necessary (if necessary) to satisfy heap properties **/
void remove(int arr[], int specItem)
{
findSpecificItem(arr, specItem);
if(found) //if the value was found in the loop
{
swap(arr[temp], arr[currentSize]);
showBinaryHeap2(1,0); // just shows what is going on before resort and delete
// in other words shows that the swap happened
while(arr[temp] < arr[temp/2])
{
if(arr[temp] < arr[temp/2]) // if the swapped value is less than it's parent
{ //// then we will run through this loop (percUp) until heap property is satisfied
swap(arr[temp], arr[temp/2]); // swap the the value with it's parent
temp = temp/2; // reset the temp value
}
}
while(arr[temp] > arr[temp*2] && arr[temp] > arr[temp*2+1])
{
if(arr[temp*2] > arr[temp*2+1]) // if left child is greater than the right child
{
swap(arr[temp], arr[temp*2+1]); // swap value with it's left child
temp = temp*2; // reset temp's value to stay accurate
}
else
{
swap(arr[temp], arr[temp*2]); // swap value with it's right child
temp = temp*2+1; // reset temp's value to stay accurate
}
}
if(arr[temp] > arr[temp*2]) // if the swapped value is greater than it's left child
{
swap(arr[temp], arr[temp*2]); // swap value with it's left child
temp = temp*2; // reset temp's value to stay accurate
}
else if(arr[temp] > arr[temp*2+1]) // if the swapped value is greater than it's right child
{
swap(arr[temp], arr[temp*2+1]); // swap value with it's right child
temp = temp*2+1; // reset temp's value to stay accurate
}
--currentSize; // decrease the size of the heap
cout <<"\nHeap after selected item is deleted: \n";
}
}
/**findSpecificItem function searches the heap for the passed data value**/
void findSpecificItem(int arr[], int specItem)
{
temp = 0;
for(int i = 1; i <= currentSize; i++) // loop to find the item in the heap
{
if(arr[i] == specItem) //if the array[index from the loop] is equal to the value
{
found = true; //sets the found flag to true
temp = i; //sets the temp to the index from the loop
}
}
if(found)
{
cout << "The item " << specItem << " was found!\n\n\n"; // tells you it was found
}
else //the item was not found in the for loop
{
cout << "Item was not found!\n\n\n"; // tells you it was not found
}
}
/**insert function fills heap with passed data**/
void insert(int arr[], int data)
{
int newLeaf = currentSize + 1; //sets the hole to the index after the last entry
int parent; //parent item used to store the index of the parent of the hole
bool placed = false; // flag to see if data item is placed in the heap
if(currentSize == 0) // test to see if the heap is empty
{
arr[newLeaf] = data; // if the heap is empty the data item is placed in the hole
placed = true; // flag placed true skips while loop
}
while(placed == false) // while the data item is not placed in the heap
{
parent = newLeaf / 2; // set the parent of the newLeaf
if(arr[parent] < data) // check to see if the parent is < the data item
{
arr[newLeaf] = data; // the data is placed in the newLeaf
placed = true; // flag placed true ends while loop
}
else // if the parent is !< the data
{
arr[newLeaf] = arr[parent]; // move the data from the parent down into the newLeaf
newLeaf = parent; // change the newLeaf to take the parents spot
}
}
currentSize++; //increment the currentSize to adjust for newLeaf
}
/**deleteMin function removes the minimum element from the heap**/
void deleteMin(int arr[], int num)
{
//int i = 1;
int emptyLeaf = arr[currentSize];
int newLeaf = 1;
bool placed = false;
for(int i = 0; i <= num; i++)
{
while(!placed)
{
left(newLeaf);// = newLeaf * 2;
right(newLeaf);// = newLeaf * 2 + 1;
// if (left(newLeaf) < currentSize && right(newLeaf) < currentSize)
// {
if(left(newLeaf) > emptyLeaf && right(newLeaf) > emptyLeaf)
{
arr[newLeaf] = emptyLeaf;
placed = true;
}
else
{
if(arr[left(newLeaf)] < arr[right(newLeaf)])
{
arr[newLeaf] = arr[left(newLeaf)];
newLeaf = left(newLeaf);
}
else
{
arr[newLeaf] = arr[left(newLeaf)];
newLeaf = left(newLeaf);
}
}
// }
}
currentSize = --currentSize;
}
}
/**readInput function reads data from file and passes it to the heap by calling the insert function**/
void readInput()
{
//string input;
int input; // variable used for reading input from a file
ifstream infile("data.txt");
if(infile.is_open()) // if the data.txt file is open
{
while(!infile.eof()) // until the end of the file is reached
{
//getline(infile, input);
infile >> input; // read input from file one item at a time
insert(binaryHeap, input); // insert each input item into the heap
print(binaryHeap);
}
infile.close();
cout << endl;
}
else
{
cout << "Error reading file!" << endl;
exit(1);
}
}
If you are experiencing a similar issue, please ask a related question
Title | # Comments | Views | Activity |
---|---|---|---|
How to find missing packages when using Netbeans IDE 8.1 ? | 19 | 46 | |
C++ standard library based binary archive format | 6 | 91 | |
object oriented programming on screen browser tutorial lesson | 2 | 76 | |
Should CArray be used for a list of pointers in C++? | 19 | 97 |
Join the community of 500,000 technology professionals and ask your questions.
Connect with top rated Experts
21 Experts available now in Live!