When you redirect via wp_safe_redirect, this is done by sending a header to the browser containing the URL to redirect to. If any content has been sent to the browser before trying to send this header, you get the headers already sent error. Once content goes to the browser, happy header time is over, no more headers can be sent.
The solution is your code must run before any content goes to the browser, hook it to an action that executes before WordPress starts rendering the page.