Given a simple undirected graph G=(V, E), the density of a subgraph on vertex set S is defined as a ratio between the number of edges |E(S)| and the number of vertices |S|, where E(S) is the set of edges induced by vertices in S. Finding the maximum density subgraph has become an intense study in recent years, especially in the social network era. Being based on a greedy algorithm that connects with a suitable graph data structure, we have reduced its time complexity by using a randomized binary search tree, also called treap. We make the complexity analysis in both time and memory requirements, including computational experiments in large scale real networks.