Thread: Help With Heaps

  1. #1
    Registered User
    Join Date
    Oct 2001
    Posts
    44

    Help With Heaps

    hi there,

    I have writeen these three files from notes given in class and by taking bits and peices from books and online. I am compiling these in borland 5.01 and im getting an error saying:

    "Heap.cpp(5,2):Cannot Creat Pre-compiled header: code in header"

    I think all the code is correct but any advice would be greatly rercieved.

    The program should turn the given array into a heap and then show how a char is added and removed from the heap.

    Thanking You,

    ps. Hope i posted the code ok....

    DAVE.


    heapTest1.cpp
    Code:
    #include "heap.cpp"
    
    void main()
    {
       Heap h;
       int i = 0;
       char s[] = "EASYQUESTION";
    
       while( s[i] != '\0')
       {
          h.insert( (int) s[i]);
          ++i;
       }
    
       h.displayAsChars();
    
       cout << "\nRemoving " << (char) h.remove() << "\n";
       h.displayAsChars();
    
       cout << "\nInserting X and B into heap\n";
       h.insert( (int) 'X');  h.insert( (int) 'B');
       h.displayAsChars();
    }
    Heap.hpp

    Code:
    #ifndef _heap_hpp
    #define _haep_hpp
    
    #include <iostream.h>
    #include <limits.h>
    #include <math.h>
    
    #define maxH 100
    
    class Heap
    {
    	private:
       		int *a;
             int N;
             void siftUp(int k);
             void siftDown(int k);
    
       public:
       		Heap();
             Heap(int);
             Heap(int[], int);
    
             void insert(int x);
             int remove();
    
             void display();
             void displayAsChars();
    };
    
    #endif
    Heap.cpp
    Code:
    #include "heap.hpp"
    #include <iostream.h>
    
    Heap::Heap()
    {
    	N = 0;
       a = new int[maxH+1];
    }
    
    Heap::Heap(int size)
    {
    	N = 0;
       a = new int[size + 1];
    }
    
    Heap::Heap(int b[], int size)
    {
    	N = size;
       a = b;
    
       for ( int i = N/2 ; i >= 1 ; --i)
       {
       	siftDown(i);
       }
    }
    
    void Heap::siftUp( int k)
    {
    	int v = a[k];
       a[0] = INT_MAX;
    
       while(v > a[k/2])
       {
       	a[k] = a[k/2];
          k = k/2;
       }
    
       a[k] = v;
    }
    
    void Heap::siftDown (int k)
    {
    	int v, j;
       v = a[k];
    
       while(k <= N/2)
       {
       	j = 2 * k;
    
          if(j < N && a[j] < a[j+1])
          {
          	++j;
          }
    
          if (v >= a[j])
          {
          	break;
          }
    
          a[k] = a[j];
          k = j;
       }
    
       a[k] = v;
    }
    
    void Heap::insert(int x)
    {
    	a[++N] = x;
       siftUp(N);
    }
    
    int Heap::remove()
    {
    	a[0] = a[1];
       a[1] = a[N--];
       siftDown(1);
       return a[0];
    }
    
    void Heap::displayAsChars()
    {
    	cout << (char)a[1] << endl;
    
       for( int i = 1 ; i <= N/2 ; i = i * 2)
       {
    
       	for( int j = 2*i ; j < 4*i && j <= N ; ++j)
          {
          	cout << (char) a[j] << "  ";
          }
    
          cout << endl;
       }
    }
    
    
    void Heap::display()
    {
    	cout << a[1] << endl;
    
       for( int i = 1 ; i<= N/2 ; i = i * 2)
       {
    
          for( int j = 2*i ; j < 4*i && j <= N ; ++j)
          {
          	cout << a[j] << "  ";
          }
    
          cout << endl;
       }
    }
    Dangerous Dave

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    > #include "heap.cpp"
    Don't include source code with #include (this is the cause of the warning)
    Include the .h file instead, then compile several files using

    bcc32 heap.cpp heaptest1.cpp

    And yes, main always returns an int, never void.

    > #ifndef _heap_hpp
    > #define _haep_hpp
    1. symbols which begin with an underscore are reserved - you should not use them
    2. watch the spelling in the #define if you hope to achieve the effect you want

  3. #3
    Registered User
    Join Date
    Oct 2001
    Posts
    44
    Ok,

    I got the spelling error in the #define and changed main() to return a int.

    I dont understand what you maen by include the .h file as i dont have any .h files. i have 2 .cpp and a .hpp. And could you tell me what you mean by compiling several files?

    And with regard to the underscores, that part of the code was provided in class, and if you could provide some alternatives i will use one of them.

    Thanks for the quick reply.

    DAVE.

    Thanks.
    Dangerous Dave

  4. #4
    30 Helens Agree neandrake's Avatar
    Join Date
    Jan 2002
    Posts
    640
    just include the hpp file, not the cpp file. when you compile both files, they are linked. the whole reason behind the #ifndef/#endif inside the header file (hpp for your case), is to avoid linking errors when you have multiple cpp files that include the same file.

    down to it, just include the hpp file from your main cpp, don't include heap.cpp, cpp files should never be included (i have a feeling that someone like Prelude will be stopping by to show me that cpp files can be included at times).
    Environment: OS X, GCC / G++
    Codes: Java, C#, C/C++
    AOL IM: neandrake, Email: neandrake (at) gmail (dot) com

  5. #5
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    > I dont understand what you maen by include the .h file as i dont have any .h files. i have 2 .cpp and a .hpp.
    Because calling C++ header files .hpp died a long time ago

  6. #6
    chococoder
    Join Date
    Nov 2004
    Posts
    515
    Do you have to use BC5.01? It's a very old compiler which doesn't conform to the current language standards.

    P.S. there's an update to 5.02 available on ftp.borland.com somewhere that fixes some bugs.

    P.P.S. has anyone managed to successfully integrate the 5.5 compiler into the 5.0x IDE? That would bring it up to the current standards (or at least far more so than the 1998 level compiler included in the 5.0 releases).

  7. #7
    Registered User
    Join Date
    Oct 2001
    Posts
    44
    Ok i just got the code working, so i take it what you guys were saying is dont use 3 files use 2. I got rid of the heapTest1.cpp and pastes all that code into the heap.cpp file. I then removed the #ifndef/#endif from the header file, as i geathered it was unnecisary when only useing 2 files. Here is the working code. Thanks.

    Ill be needing a lot more advice soon as im writing a heap program to sort towns according to their distancse from the capital of a country. Ill post code when i have it written.

    Heap.cpp
    Code:
    #include "heap.h"
    #include <iostream.h>
    
    
    void main()
    {
       Heap h;
       int i = 0;
       char s[] = "EASYQUESTION";
    
       while( s[i] != '\0')
       {
          h.insert( (int) s[i]);
          ++i;
       }
    
       h.displayAsChars();
    
       cout << "\nRemoving " << (char) h.remove() << "\n";
       h.displayAsChars();
    
       cout << "\nInserting X and B into heap\n";
       h.insert( (int) 'X');  h.insert( (int) 'B');
       h.displayAsChars();
    }
    
    
    Heap::Heap()
    {
    	N = 0;
       a = new int[maxH+1];
    }
    
    Heap::Heap(int size)
    {
    	N = 0;
       a = new int[size + 1];
    }
    
    Heap::Heap(int b[], int size)
    {
    	N = size;
       a = b;
    
       for ( int i = N/2 ; i >= 1 ; --i)
       {
       	siftDown(i);
       }
    }
    
    void Heap::siftUp( int k)
    {
    	int v = a[k];
       a[0] = INT_MAX;
    
       while(v > a[k/2])
       {
       	a[k] = a[k/2];
          k = k/2;
       }
    
       a[k] = v;
    }
    
    void Heap::siftDown (int k)
    {
    	int v, j;
       v = a[k];
    
       while(k <= N/2)
       {
       	j = 2 * k;
    
          if(j < N && a[j] < a[j+1])
          {
          	++j;
          }
    
          if (v >= a[j])
          {
          	break;
          }
    
          a[k] = a[j];
          k = j;
       }
    
       a[k] = v;
    }
    
    void Heap::insert(int x)
    {
    	a[++N] = x;
       siftUp(N);
    }
    
    int Heap::remove()
    {
    	a[0] = a[1];
       a[1] = a[N--];
       siftDown(1);
       return a[0];
    }
    
    void Heap::displayAsChars()
    {
    	cout << (char)a[1] << endl;
    
       for( int i = 1 ; i <= N/2 ; i = i * 2)
       {
    
       	for( int j = 2*i ; j < 4*i && j <= N ; ++j)
          {
          	cout << (char) a[j] << "  ";
          }
    
          cout << endl;
       }
    }
    
    
    void Heap::display()
    {
    	cout << a[1] << endl;
    
       for( int i = 1 ; i<= N/2 ; i = i * 2)
       {
    
          for( int j = 2*i ; j < 4*i && j <= N ; ++j)
          {
          	cout << a[j] << "  ";
          }
    
          cout << endl;
       }
    }
    Heap.h
    Code:
    #include <iostream.h>
    #include <limits.h>
    #include <math.h>
    
    #define maxH 100
    
    class Heap
    {
    	private:
       		int *a;
             int N;
             void siftUp(int k);
             void siftDown(int k);
    
       public:
       		Heap();
             Heap(int);
             Heap(int[], int);
    
             void insert(int x);
             int remove();
    
             void display();
             void displayAsChars();
    };
    Dangerous Dave

  8. #8
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    > so i take it what you guys were saying is dont use 3 files use 2
    NO!!!!
    3 files were just fine - it's just a matter of getting the correct contents in each file.

    Sooner or later, you need to figure out multi-file projects (my current one at work has 1800 files), so now is the time to practice getting it right.

  9. #9
    chococoder
    Join Date
    Nov 2004
    Posts
    515
    in this case:
    heap.h
    heap.cpp (containing the functions declared in heap.h and anything they need internally)
    heaptest.cpp (test program)

    If heap.cpp gets very big you may want to divide it into functional modules as well.

    BC5 makes it easy to have multiple sourcefiles in a project. No messing with makefiles or terribly long commandlines, the IDE will generate that for you behind the scenes (though it can generate the makefile if you're curious, see project->generate makefile in the IDE).

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, 03:09 PM
  2. Buffers , heaps , stacks ...
    By BlaX in forum C Programming
    Replies: 1
    Last Post: 02-17-2009, 01:11 PM
  3. Heaps!
    By Leojeen in forum C Programming
    Replies: 18
    Last Post: 11-26-2008, 01:31 AM
  4. Help with heaps?
    By Nornny in forum C++ Programming
    Replies: 4
    Last Post: 03-22-2004, 12:19 PM
  5. FAQ heaps
    By face_master in forum FAQ Board
    Replies: 2
    Last Post: 10-06-2001, 11:21 AM