First, a word about terminology: the heap is the memory space manipulated by the functions malloc, calloc, realloc, free and their friends from the C standard library. They exist in C++ for backwards compatibility reasons with C89 programs, but in practice are not used because they do not "fit in" with the C++ philosophy.

The new operator in C++, which is used for performing memory allocation by hand (something not done very often) works on the free store, a memory space reserved to the C++ language. If you're using C++ and want to allocate memory dynamically, you should be using the free store, and not the heap.

Now, here's the trick: in C++, creating an object is done in three different ways. Either you 1° create a variable of the object's type (at which point, the object dies when the variable goes out of scope); or 2° you create a member of the object's type in another object, either one of your own, or a standard library container (so the object dies when the object who contains it dies); or 3° you allocate the object on the free store using new (at which point the object dies when you delete it).

Techniques 1° and 2° are sufficient for 99% of all cases you might encounter. The only situation where 3° is useful is when you wish to return a new object (and cannot afford to return it by value so that it gets copied), at which point the typical approach is to create the object dynamically so that it can outlive the function it was born in (something not possible with techniques 1° and 2°) and return a pointer or reference to it.

I personally advise returning either an std::auto_ptr (the default choice when returning pointers, because it prevents memory leaks) or boost::shared_ptr (if you know that your object will be kept around and shared by many users).