Find all files (type f) with any name (name '*.*') and print them (print0) in a sorted order (sort -z) and for each file (xargs -0 -n 1) run the command head -n 1 in parallel (P 4)
find . -type f -name '*.*' -print0 | sort -z | xargs -0 -n 1 -P 4 head -n 1