How to free space after deleting the millions of rows from a table
alter table TABLENAME move;


followed by rebuilding the indexes on that table should do what you want.

After 'moving' the table around, the indexes for the rows will become unusable (as you can verify with something like):

select index_name, status from all_indexes 
 where table_name = 'TABLENAME' and
       owner      = 'SOMEUSER';


So, you would rebuild such an unusable index with a

alter index TABLENAME_IX_01 rebuild;