By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
440,823 Members | 730 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 440,823 IT Pros & Developers. It's quick & easy.

Heap, how to insert?

P: 2
The purpose of the Insert function is to add a new integer in the Heap assuming that it is not already full. If Heap capacity has been reached, it attempts to double the current capacity. If capacity cannot be doubled, it throws FullHeap.

Here is the Heap.h file
const int MAXSIZE = 4; // Default maximum heap size
class Heap // Smart Heap ADT as an array
{
private:
int* ptr; // Pointer to smart heap array
int maxsize; // Current maximum heap size
int num; // Current number of elements in heap
void Swap(int& a, int& b); // Swaps integers a and b

public:
Heap(); // Creates empty smart heap of MAXSIZE

~Heap();

void ReheapDown(int root, int bottom); // Repairs heap order property from root to leaf


void ReheapUp(int root, int bottom); // Repairs heap order property from leaf to root


bool IsFull();

bool IsEmpty();

void Insert(int n); // Inserts n into heap, doubling heap capacity if needed.


int DeleteMax(); // Deletes and returns max value from heap if heap not empty


void MakeEmpty(); // Makes heap empty

void Print(); // Write heaparray to stdout

int Size(); // Returns current number of element in heap

int Capacity(); // Returns current heap capacity
};

I'm not quite sure how to double the heap capacity.
Here is what I have for the Insert function.
void Heap::Insert(int n)
{
if (num==maxsize)
{
maxsize=maxsize*2;
int* newptr;
int i=0;
newptr=new int[maxsize];
while(i<num)
{
newptr[i]=ptr[i];
i++;
}
num++;
ptr[num-1]=n;
ReheapUp(0,num-1);
}
else
{
num++;
ptr[num-1] = n;
ReheapUp(0,num-1);
}
}

I got a segmentation fault here.
Nov 21 '08 #1
Share this Question
Share on Google+
4 Replies


10K+
P: 13,264
An easy way to learn is to use cout statements in your code to find what the values of your variables are against what you are expecting them to be.
Nov 21 '08 #2

P: 63
Expand|Select|Wrap|Line Numbers
  1.     while(i<num)
  2.     {
  3.     newptr[i]=ptr[i];
  4.     i++;
  5.     }
  6.     num++;
  7.     ptr[num-1]=n;
  8.     ReheapUp(0,num-1);
  9.     }
  10.  
you want to add the following lines before num++

Expand|Select|Wrap|Line Numbers
  1. delete [] ptr;
  2. ptr = newptr;
  3.  
The reason you are getting a segfault is that you are trying to add an element to your old ptr, which is still of old size. newptr is of doubled size, but you are not using it yet. If you add the lines, the doubled space, address of which is stored in newptr, gets assigned to ptr.
Nov 21 '08 #3

weaknessforcats
Expert Mod 5K+
P: 9,197
How come your heap is an array?

I would have expected you would have a node containing the allocation information and that node would be in a heap data structure.
Nov 21 '08 #4

P: 2
Thanks so much vmpstr!
It works!!
Nov 21 '08 #5

Post your reply

Sign in to post your reply or Sign up for a free account.