Thread: Help with heaps?

Hi guys, I'm brand brand new to this forum, so excuse me if I make any newbie mistakes. I try to look over the FAQs and important posts before posting, but you're still forewarned. Anyways, I'm working on a homework assignment for a second-semester Intro to CS class and we have to make a heap with an array of size 20 which stores the smallest priority on the top. So it's just a min-heap. But for some reason, I get a segmentation fault/ assertion failed because I believe my left() function is wrong. Also, my insert() function isn't resorting the heap after an object is inserted and I don't think my reheapify function is in any working order either. I have such a hard time proofreading my work and was wondering if I could get some second eyes for help.

Code:

Heap::Heap() {
  heapSize = 0;

  int t = 0;

  while (t < heapMaxSize) {
    array[t].priority = -1;
    t++;
  }

}
int Heap::left(int p) const {
  assert(p < (heapSize - 1)/2);
  return (p * 2) + 1;
}

int Heap::right(int p) const {
  assert(p < (heapSize - 1)/2);
  return (p * 2) + 2;
}

int Heap::parent(int p) const{
  assert (p != 0);
  return (p - 1) / 2;
}

void Heap::insertHeapItem(int i) {
  if (isFull())                  // Stack Overflow exception
    cout << "Error: Stack Overflow Error \n";  // FIX THIS LATER

  HeapItem newItem;              // Creates new item
  newItem.priority = i;          // Sets priority

  array[heapSize] = newItem;     // next open array position gets item

  int positionNew = heapSize;    // Moves position up one
  heapSize++;                    // increments size

  // while positionNew is not the root and is greater than its parent
  while (positionNew != 0 and (array[positionNew].priority 
	 < array[parent(positionNew)].priority)) {

    swap(array[positionNew], array[parent(positionNew)]);  // Swap positions
    positionNew = parent(positionNew);
  }  
}

HeapItem Heap::removeMin() {
  assert (!isEmpty());

  heapSize--;

  if (heapSize != 0) {   // If there's more than just the  root
    swap(array[0], array[heapSize]);   // Switch largest with smallest 
    reHeap(0);                         // rearrange to proper places
  }
  return array[heapSize];        // Take off last(lowest) heap item

}
void Heap::reHeap(int p) {

  int leaf = left(p);

  if ((array[leaf].priority > array[leaf + 1].priority) and
      (leaf < heapSize - 1))
    leaf++;

  if (array[p].priority <= array[leaf].priority)
    ;

  swap(array[p], array[leaf]);
  reHeap(leaf);
}

void Heap::swap(HeapItem a, HeapItem b) {
  HeapItem temp = a;
  a = b;
  b = temp;
}

HeapItem is a separate class with just an int that's called priority.

If you're looking to see my driver, here is the code:

Code:

int main() {

  Heap test;
  HeapItem temp;
  int n = 0;

  test.insertHeapItem(3);

  while (n < heapMaxSize) {
    cout << test.priority(n) << " ";
    n++;
  }
  cout << '\n';
  n = 0;

  test.insertHeapItem(20);

  while (n < heapMaxSize) {
    cout << test.priority(n) << " ";
    n++;
  }
  cout << '\n';
  n = 0;

  test.insertHeapItem(1);

  while (n < heapMaxSize) {
    cout << test.priority(n) << " ";
    n++;
  }
  cout << '\n';
  n = 0;

  temp = test.removeMin();

  cout << '\n' << temp.priority;

  return 0;
}

Thank you so much for any help in advance!

left(), right(), and parent() all return correct values, but the assert in left() is incorrect.

>>heapSize = 0;
>>int t = 0;
>>while (t < heapMaxSize)
How many times will that loop?

>>void Heap::swap(HeapItem a, HeapItem b)
This swaps nothing since a and b are passed by value.

For any heap algorithm problems, my best suggestion is that you go back and really study your book. If you don't understand it, ask your professor for help.

gg

Thank you so much for your help. I'll be sure to talk to my professor soon, but thank you for catching my logical errors. Might I ask what is the correct assertion for left() if you're willing to give it? Been scratching my brain, and I think I'm just overthinking it.

>> ... and I think I'm just overthinking it.
Personally, I would have done a more straight forward bounds check for both left() and right():

Code:

int Heap::left(int p) const 
{
   int i = (p * 2) + 1; 
   assert((i > 0) && (i < heapSize));
   return i;
}

Using your current approach it should be
>> assert(p < (heapSize/2));

gg

Hi again, thank you so much for your help again. I still run my testheap program and the assertion still fails in my left function. However, I do believe it's because my removeMin() and/or reHeap() functions are wrong. I'm reposting just that code for reference. Could someone tell me if I went logically wrong or any typos with this? Thank you so much again!

Code:

HeapItem Heap::removeMin() {
  assert (!isEmpty());

  heapSize--;

  if (heapSize != 0) {   // If there's more than just the  root
    swap(array[0].priority, array[heapSize].priority);   
    // Switch largest with smallest 
    reHeap(0);                         // rearrange to proper places
  }
  return array[heapSize];        // Take off last(lowest) heap item

}
void Heap::reHeap(int p) {

  int leaf = left(p);

  if ((array[leaf].priority > array[leaf + 1].priority) and
      (leaf < heapSize - 1))
    leaf++;

  if (array[p].priority <= array[leaf].priority)
    ;

  swap(array[p].priority, array[leaf].priority);
  reHeap(leaf);
}