The headers are sent once the script has sent any output to the user - whether that output was generated by PHP or HTML/text contained in the script. What you have to keep in mind is that even a blank line can generate output. The easiest way to prevent the issue is to begin the script with "<?php" at the very top, and use "?><!DOCTYPE " to begin the HTML, with only PHP code in-between.
Whether or not all of your PHP code belongs above the <!DOCTYPE> is largely a matter of organization and convenience, in my opinion. Generally, you'll want to process most of the form submission data at the very beginning so you can do validation and any other necessary processing before any HTML is produced. I also tend to include local functions in this area just to make updating and debugging a little easier.
I've never been a fan of having the same file/script contain both the form and the processing code. I understand the convenience, but it's just never felt right to me, regardless of what might be considered best practice. And if you have multiple forms on the same page, I'd expect it to be easy for the code to become very convoluted and difficult to maintain. But, as I say, I'm biased.