The Department is basically a way to group your learners for reports and enrollment. This is similar to the other reporting filters of Job Titles, User Locations and the Custom Fields 1,2 and 3 that can be customized. Users from different Departments can be located in the same Hierarchy folder, if needed.
The Hierarchy is designed to give your supervisors access to the employees under them based on the level of Supervisor Permissions given. The hierarchy also determines who may receive the warning emails as well. Your Hierarchy should be grouped based on which supervisors need to have access to the folder of employees.