467,168 Members | 1,027 Online
Bytes | Developer Community
Ask Question

Home New Posts Topics Members FAQ

Post your question to a community of 467,168 developers. It's quick & easy.

Heap, how to insert?

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
  • viewed: 9031
Share:
4 Replies
8TB
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
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 8TB
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
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.

Similar topics

2 posts views Thread by mordac | last post: by
5 posts views Thread by Ook | last post: by
3 posts views Thread by silver360@gmail.com | last post: by
1 post views Thread by Chris Mullins | last post: by
reply views Thread by not_a_commie | last post: by
16 posts views Thread by Jon Harrop | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.