How to change website’s header frontend layout?

we were just given a new UI for our website and we need to make some radical changes to our theme; one of them being changing the header’s container from one colum-horizontal to 3 columns-vertical.

We basically need to divide the header container in 3 columns in which the first one on the left contains the logo with the categories/menu, the one in the center is empty and the last column on the right side contains icons like shopping cart, user and wishlist, all displayed vertically.

Can anyone give me any hints on how to approach this? Thank you so much.

here are some ui templates to help:

1. current layout
   

2. new layout