Aims: Fundamental to any theory of high-mass star formation are gravity and turbulence. Their relative importance, which probably changes during cloud evolution, is not known. By investigating the spatial and density structure of the high-mass star-forming complex NGC 6334 we aim to disentangle the contributions of turbulence and gravity. Methods: We used Herschel PACS and SPIRE imaging observations from the HOBYS key programme at wavelengths of 160, 250, 350, and 500 μm to construct dust temperature and column density maps. Using probability distribution functions (PDFs) of the column density determined for the whole complex and for four distinct sub-regions (distinguished on the basis of differences in the column density, temperature, and radiation field), we characterize the density structure of the complex. We investigate the spatial structure using the Δ-variance, which probes the relative amount of structure on different size scales and traces possible energy injection mechanisms into the molecular cloud. Results: The Δ-variance analysis suggests that the significant scales of a few parsec that were found are caused by energy injection due to expanding H ii regions, which are numerous, and by the lengths of filaments seen everywhere in the complex. The column density PDFs have a lognormal shape at low densities and a clearly defined power law at high densities for all sub-regions whose slope is linked to the exponent α of an equivalent spherical density distribution. In particular with α = 2.37, the central sub-region is largly dominated by gravity, caused by individual collapsing dense cores and global collapse of a larger region. The collapse is faster than free-fall (which would lead only to α = 2) and thus requires a more dynamic scenario (external compression, flows). The column density PDFs suggest that the different sub-regions are at different evolutionary stages, especially the central sub-region, which seems to be in a more evolved stage. Herschel is an ESA space observatory with science instruments provided by European-led Principal Investigator consortia and with important participation from NASA.Appendix A is available in electronic form at http://www.aanda.orgRead less <