Solved

How can I fix a heap after deleting specific items?

Posted on 2009-05-12
22
374 Views
Last Modified: 2013-12-14
In what I have so far the user is prompted to select a number to remove from the heap.  I believe that this is working just fine now.  In order to do that I percolate the item up to the root and call deleteMin to remove it.  The problem lies here, the heap is now most likely in violation of the heap property.  This is the biggest issue.

I also have a minor issue.  It's more of a curious thing than anything else.  If you will notice I have written a showBinaryHeap function.  This is supposed to print the heap showing the structure.  What I have written is very ugly and obviously doesn't resize to match the current size of the heap.  I was wondering if anyone might have any ideas on how to improve this an d make it more robust.

Other than these two things I think everything may be under control at this time....
Of course my code is very sloppy right (at least I think so), so I may have some other issues that may be BAD.

Oh, and since the text file I'm using only has a few items in it I will just write the contents of the file here:                     10,12,1,14,6,5,8,15,3,9,7,4,11,13,2

Thanks for any help you provide!
#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);

    }

}

Open in new window

0
Comment
Question by:b_acs
  • 10
  • 7
  • 3
22 Comments
 
LVL 39

Assisted Solution

by:itsmeandnobodyelse
itsmeandnobodyelse earned 166 total points
Comment Utility
As far as I could see there is a mix-up as you were using an 0-based array but store 1-based. For example your first entry is not at slot 0 of the heap array but at slot 1. But the currentsize is 1. In deleteMin you have

    int emptyLeaf = arr[currentSize];

what therefore doesn't point to an empty slot but to the last slot.



0
 
LVL 53

Accepted Solution

by:
Infinity08 earned 334 total points
Comment Utility
>> In order to do that I percolate the item up to the root and call deleteMin to remove it.

How do you do that without breaking the heap property ?

>> The problem lies here, the heap is now most likely in violation of the heap property.

Indeed. Moving a value that is not the minimum to the root of the min-heap doesn't sound sensible, because the root has to be the minimal element at all times.

So, what you do instead, is identify two nodes :

(a) the node A that holds the value to be removed
(b) the node B that is the right-most node on the lowest level of the heap

Then :

1) You take the value from node B, and place it in node A
2) You remove node B from the heap (there's no problem with this, since removing it doesn't change any of the properties of the heap)
3) All that's left to do, is to sift the current value in node A up or down, depending on whether it's smaller or bigger than its parent or child node resp. Keep doing this until that value is in place.

That's all.

I didn't check your code, but from your description, I understand that you were using the wrong algorithm. If so, you'll have to modify the code to use the correct algorithm.
0
 

Author Comment

by:b_acs
Comment Utility
Hmm....not sure what you are getting at.  Are you saying I could have an out of bounds error?

I know that it is not pointing to an empty slot.  The point is that after deleting the minimum index the last slot will be empty.  I don't see a problem with this.

It's only when I move things around that I have an issue.  I'm thinking I need to figure out how to reheapify the heap after I call remove().
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
Comment Utility
>>>> Hmm....not sure what you are getting at.  Are you saying I could have an out of bounds error?

I don't know whether that is a response to my comment or to that of Infinity, but in case it is directed to me, the answer is yes.

I couldn't see any statement  in your code where you checked the total heap-size like

  if (currentSize >= sizeof(binaryHeap)/sizeof(binaryHeap[0])  
  {
        cout << "the heap is full" << endl;
        exit(1);
  }

But that is only a problem if inserting more than 127 numbers. The bigger problem are statements like

     for(int i = 0; i <= num; i++)

where you run a cycle num+1 times but most probably only want to run it num times.

Here the issue that you have a 0-based index of the array but your current code use it as 1-based will spoil some of your conditions. IMO, the only senseful way out is to consequently change your heap-management to be 0-based, e. g. in your insert function you would start with

    int newLeaf = currentSize;  //sets the hole to the index after the last entry

what also would make the comment true (which now is false at begin).

Another problem is that you didn't initialize some of your variables. Especially the heap array is not initialized what might not give problems for your tests as the debugger probably would make all zeros. But in release mode your heap array could have arbitrary contents. Then statements like
 
>>>> int emptyLeaf = arr[currentSize];

could have any garbage contents even negative numbers. Then comparisions like

>>>> if(left(newLeaf) > emptyLeaf && right(newLeaf) > emptyLeaf)

necessarily must fail whereat I don't know the purpose of that statement anyhow. If the emptyLeaf is supposed to be 0, then all slots should have a contents greater 0 and the if statement always is true *or* the emptyLeaf is supposed to be the contents of the last entry of the heap. Then the name 'emptyLeaf' is more than poor and the condition most likely false for almost all slots as your heap organisation would produce an almost sorted array. In any case you should make it clear what your algorithm is and do a proper naming so that others could keep track on it either.
0
 

Author Comment

by:b_acs
Comment Utility
Now this may sound crazy, but I have been thinking and logically it sounds like this would work:

find the value to be removed from heap
swap that with the last node or slot
delete the last node or spot

this would be the same as:
swapping the value to be removed with the root node
then swapping the new root with the last entry (which can now be removed)
then just percolating up  and then back down the heap

from a few checks i just did the item being percDown seems to always end up in the original location of the node with the value to be removed
0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
Why not do it the normal way ? (the way I described it, and the first way in your previous post)
0
 

Author Comment

by:b_acs
Comment Utility
well from what I can tell doing it the "normal way" is exactly the same as doing it the way I described
When the value of Node B is placed into node A, the heap property should still be intact.

So there is no other sifting needed.
0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
>> well from what I can tell doing it the "normal way" is exactly the same as doing it the way I described

>> swapping the value to be removed with the root node

You don't swap the value to be deleted with the root node's, but with the rightmost node on the lowest level. That's the normal way ;)


>> So there is no other sifting needed.

There is, because the heap property needs to be preserved. Once the value is swapped, the value will have to be sifted up or down as needed.
0
 

Author Comment

by:b_acs
Comment Utility
          4
      2
           5
 1  
           7
      3
           6

Ok I will use this simple heap to explain what I mean....
(btw when I was talking about the root node that was just an explanation of how I proved this to myself)
Let's say we want to remove the 3.
We swap the 3 with the last node:
           3
      2
           5
 1  
           7
      4
           6

As you can see the heap property is still satisified and we can remove the last node now without any fear.  I have worked on this and have yet to come up with an instance where this won't work.

Explain to me the folly of my ways if I'm wrong...
0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
>> As you can see the heap property is still satisified and we can remove the last node now without any fear.  I have worked on this and have yet to come up with an instance where this won't work.

Ok. Here is one :

                       1
              10            20
          13    16    23    26

Try removing the 10 the same way you tried removing the 3 in your example.
0
IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

 

Author Comment

by:b_acs
Comment Utility
I see, so really you should never have to sift up except in very rare cases, but you may need to sift down after the swap to satiisfy the heap property.
Thank you for clearing that up for me.

So this is more appropiate....
		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;

Open in new window

0
 

Author Comment

by:b_acs
Comment Utility
Except now that I think about it, that will only work if only one swap is necessary to make the heap property valid.....
still need a loop or possibly changing the logic a little and calling a function recursively
0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
>> so really you should never have to sift up except in very rare cases,

Here's an example for you :

                       1
              30            20
          33    36    23    26

Try to remove the 36
0
 

Author Comment

by:b_acs
Comment Utility
Argh! I can't figure out how to loop it....

Here is what I have:
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);

	}

}

Open in new window

0
 

Author Comment

by:b_acs
Comment Utility
Can anyone point to me what I have wrong now.....

I thought I was on the right track, actually I'm pretty sure I am, however I have hit a wall.
It seems trying to do a loop isn't as easy as I thought it would be.
0
 

Author Comment

by:b_acs
Comment Utility
dum da dum dum...... dum

I got it, I will post the code a little later, since I am working on a different machine without net access to compile.

As for my other question..... I'm still interested if anyone can come up with a way to print the heap showing it's structure.
0
 

Author Comment

by:b_acs
Comment Utility
Ok here is what I got.....

I know there are a couple of minor things that are probably wrong, so by all means let me know.

Oh and itsmeandnobodyelse, I kind of understand what you are talking about but not really.
Maybe point out specific places that I need to fix.  (Don't give me the code though)  I have been struggling a bit this term, I think because I need to work more on understanding and comprehension rather than functionality....

btw I will leave this open for a couple of days to see if anyone responds with any suggestions and also anything about the heap structure function.

Thanks
// 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);

    }

}

Open in new window

0
 
LVL 53

Assisted Solution

by:Infinity08
Infinity08 earned 334 total points
Comment Utility
1) Don't use globals to communicate between functions. Use the function arguments and return value instead.

2) For sifting the value down after deleting, you can do it a lot simpler. The direction you sift it down is the child with the smallest value. If that value is bigger than the current value, then no sifting down is needed. If it's smaller than the current value, you sift it down towards that child. No need for all those loops. Just find the smallest child, compare it, and sift down if needed, and do that in a loop.

3) For showing the heap graphically (unrotated), you first retrieve the height of the tree, from which you can derive the offset of the root node. And then it's a simple matter of iterating over each element in the array (from index 1 to the end), and showing it. The first level will start at the calculated offset, and will contain 1 item, followed by a newline. For the second level, the offset is decreased, and it will contain 2 items, followed by a newline. For the third level, the offset is decreased once more, and it will contain 4 items, followed by a newline. etc.
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
Comment Utility
>>>> Maybe point out specific places that I need to fix.
If you read my comment again, you probably will find out some concrete hints. Don't think it makes sense to repeat my comments as long as you were not ready to get yourself in for the issues I mentioned.
0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
Based on the author's post http:#24380813, he got a solution for his main problem, apparently by following my advice in http:#24372524 (and follow-up posts).

His second question (which he said was less important) has been answered by point 3) in http:#24383279.

What itsmeandnobodyelse pointed out in http:#24372262 wasn't really instrumental to answer the original question (the reason to use 1-based indexes was likely intentional, so it isn't really a problem, except that it wastes one slot in the array - the real problem is that there is no bounds checking), but it points out a possible improvement - namely checking the bounds of the array for each insert. So it might be useful to add it to the PAQ too.

In short : I quggest a PAQ for http:#24372262 (itsmeandnobodyelse), http:#24372524 (Infinity08), http:#24383279 (Infinity08)
0

Featured Post

How to improve team productivity

Quip adds documents, spreadsheets, and tasklists to your Slack experience
- Elevate ideas to Quip docs
- Share Quip docs in Slack
- Get notified of changes to your docs
- Available on iOS/Android/Desktop/Web
- Online/Offline

Join & Write a Comment

What is C++ STL?: STL stands for Standard Template Library and is a part of standard C++ libraries. It contains many useful data structures (containers) and algorithms, which can spare you a lot of the time. Today we will look at the STL Vector. …
This article will show you some of the more useful Standard Template Library (STL) algorithms through the use of working examples.  You will learn about how these algorithms fit into the STL architecture, how they work with STL containers, and why t…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

771 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

12 Experts available now in Live!

Get 1:1 Help Now