The potential of a P2P system to become an ultra-scalable and yet manageable infrastructure lies in its self-organizing nature. Being composed by increasingly powerful commodity devices, these systems must also endeavor into being not merely self-organizing, but self-adaptation as well. On this regard, aligning the hierarchy required for efficient operation with the one represented by heterogeneity nature of the nodes – an inherent attribute of any large system, in a self-adaptive fashion, thus becomes an interesting problem. We designed a set of algorithms that, collectively, can balance the routing traffic in the inherent hierarchy of an O(log N) structured P2P overlay with node capacities, by promoting more capable nodes to higher levels. Our mechanism is simple and efficient, and is completely distributed and resilient to failures. Interestingly, we found that this is only possible when all nodes are liable to contribute globally, but priorities must be given to regional interests first.