>>5 I completely spaced that.
If you do plan to use the same heat sink then you should get new thermal paste and clean off both the heat sink and CPU.
The type of cooler is totally dependent on what you want to do or use the CPU for. Any kind of overclocking, OC, or tweaking you would want to get another cooling solution. AIO water coolers are a good balance between space and cooling as well, which are easy to install too.
I would recommend testing out the CPU under loads after installing the heat sink by downloading something like HWmonitor and doing a CPU stress test. This ensures that you installed the heat sink properly and that the cooling solution is adequate for your needs.