Is the concept of OOP intimately tied to allocating objects on the heap? Is it possible to write normal OOP without creating excessive objects on the heap?
You create exactly as many objects on the heap as your program asks for. If you think that's too many, ask for fewer. You may have to throw away features. For example, my text editor has an unlimited undo buffer, for every action I do some object is stashed away that allows the text editor to undo or redo that operation. If you don't want that then remove or limit the undo feature.
But OOP is not at all responsible for these heap allocations. You would need the same number for the same functionality if you used plain procedural programming.
BTW. A decent operating system will let you create gazillions of small objects with very little overhead. Like allocating a 16 byte object with one bit of overhead. Allocating sets the bit, deallocating clears it. And then there is Objective-C which stashes small immutable objects (numbers, strings up to six characters, dates etc.) inside a 64 bit pointer so nothing is allocated at all!
Excessive, probably not, and I'd argue that well-written object-oriented code in languages like C++ doesn't have to make "excessive" use of the heap (even though unfortunately a lot of code does), but it's often difficult to make non-trivial OOP code let alone any kind of code that maintains persistent state with side effects follow a strict push/pop pattern of memory allocation/deallocation.
For example, an image editor like Photoshop might allocate an image object each time the user requests to create a new image and should deallocate the image when the user requests to close the image.
That's not even a complex OOP example involving encapsulation or polymorphism, but already we're no longer able to practically use a push/pop pattern to memory allocation and deallocation since the memory is freed upon user request, not when we exit the scope of the function that allocated the image.
Whenever you have the need to free memory in a way that's tied to external inputs determined at runtime, like user input, then you can no longer effectively use a stack allocator/data structure since it doesn't support removing from the middle of the data structure, only the front/top.
More practical to me might be a language that pools memory from a different free list for each object type, though that could end up reserving a lot of memory in advance unless we can just use it selectively for objects where it makes the most sense (ex: ones we're going to be allocating in a sufficient number).
I'd actually love to see such a language if it could come with 32-bit pointers to elements instead of 64-bits even if pointer indirection requires a bit more arithmetic, since I'm often doing that kind of stuff a lot, translating 64-bit pointers into 32-bit indices in a particular context against a particular data type when I can anticipate that I won't be needing more than 4.29 billion instances of that object.
OOP without dynamic memory is limited. You can have classes and polymorphism using statically allocated objects. However, many OOP design patterns require use of dynamic allocation and cannot be employed in a practical and useful way without dynamic memory.
For example, the factory pattern where a factory can create any number of different concrete classes, but only returns a reference to the base class. Dynamic memory allocation allows the factory to create different concrete classes where it does not know the exact type and therefore size of the object it will create until run-time when the create method is called. The code calling the create method is agnostic to the exact type created by the factory, it doesn't know about concrete types or their sizes. This eases code maintenance as the coupling is reduced and only the factory class needs to be updated when concrete classes are added or removed.
To attempt to use static memory allocation in this scenario would require the code calling the factory's create method to pre allocate the memory statically and this memory would have to be large enough for any concrete class the factory creates. This would require some very ugly workarounds and would force in coupling between the code calling the factory and all the concrete implementations of the classes that could be created and would defeat the whole purpose of the factory pattern.
That is one example, there are several other design patterns which would be non-viable without dynamic memory allocation.