Help with heaps?

This is a discussion on Help with heaps? within the C++ Programming forums, part of the General Programming Boards category; Hi guys, I'm brand brand new to this forum, so excuse me if I make any newbie mistakes. I try ...

  1. #1
    Registered User
    Join Date
    Mar 2004
    Posts
    8

    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!

  2. #2
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,652
    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

  3. #3
    Registered User
    Join Date
    Mar 2004
    Posts
    8
    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.

  4. #4
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,652
    >> ... 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

  5. #5
    Registered User
    Join Date
    Mar 2004
    Posts
    8
    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);
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Buffers , heaps , stacks ...
    By BlaX in forum Tech Board
    Replies: 9
    Last Post: 02-17-2009, 02:09 PM
  2. Buffers , heaps , stacks ...
    By BlaX in forum C Programming
    Replies: 1
    Last Post: 02-17-2009, 12:11 PM
  3. Heaps!
    By Leojeen in forum C Programming
    Replies: 18
    Last Post: 11-26-2008, 12:31 AM
  4. Help With Heaps
    By Dangerous Dave in forum C++ Programming
    Replies: 8
    Last Post: 11-23-2004, 07:47 AM
  5. FAQ heaps
    By face_master in forum FAQ Board
    Replies: 2
    Last Post: 10-06-2001, 11:21 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21