diff --git a/mercurial/commands.py b/mercurial/commands.py
--- a/mercurial/commands.py
+++ b/mercurial/commands.py
@@ -1286,11 +1286,14 @@ def heads(ui, repo, **opts):
     changesets. They are where development generally takes place and
     are the usual targets for update and merge operations.
     """
-    heads = repo.changelog.heads()
+    if opts['rev']:
+        heads = repo.heads(repo.lookup(rev))
+    else:
+        heads = repo.heads()
     br = None
     if opts['branches']:
-        br = repo.branchlookup(heads)
-    for n in repo.changelog.heads():
+        br = repo.branchlookup(list(heads))
+    for n in heads:
         show_changeset(ui, repo, changenode=n, brinfo=br)
 
 def identify(ui, repo):
@@ -2237,8 +2240,9 @@ table = {
          "hg grep [OPTION]... PATTERN [FILE]..."),
     "heads":
         (heads,
-         [('b', 'branches', None, _('find branch info'))],
-         _('hg heads [-b]')),
+         [('b', 'branches', None, _('find branch info')),
+          ('r', 'rev', None, _('show only heads descendants from rev'))],
+         _('hg heads [-b] [-r <rev>]')),
     "help": (help_, [], _('hg help [COMMAND]')),
     "identify|id": (identify, [], _('hg identify')),
     "import|patch":
diff --git a/mercurial/localrepo.py b/mercurial/localrepo.py
--- a/mercurial/localrepo.py
+++ b/mercurial/localrepo.py
@@ -613,8 +613,12 @@ class localrepository:
                 self.dirstate.update([dest], "a")
             self.dirstate.copy(source, dest)
 
-    def heads(self):
-        return self.changelog.heads()
+    def heads(self, start=nullid):
+        heads = self.changelog.heads(start)
+        # sort the output in rev descending order
+        heads = [(-self.changelog.rev(h), h) for h in heads]
+        heads.sort()
+        return [n for (r, n) in heads]
 
     # branchlookup returns a dict giving a list of branches for
     # each head.  A branch is defined as the tag of a node or
diff --git a/mercurial/revlog.py b/mercurial/revlog.py
--- a/mercurial/revlog.py
+++ b/mercurial/revlog.py
@@ -409,25 +409,23 @@ class revlog:
         assert heads
         return (orderedout, roots, heads)
 
-    def heads(self, stop=None):
-        """return the list of all nodes that have no children"""
-        p = {}
-        h = []
-        stoprev = 0
-        if stop and stop in self.nodemap:
-            stoprev = self.rev(stop)
+    def heads(self, start=nullid):
+        """return the list of all nodes that have no children
+        if start is specified, only heads that are children of
+        start will be returned"""
+        reachable = {start: 1}
+        heads = {start: 1}
+        startrev = self.rev(start)
 
-        for r in range(self.count() - 1, -1, -1):
+        for r in xrange(startrev + 1, self.count()):
             n = self.node(r)
-            if n not in p:
-                h.append(n)
-            if n == stop:
-                break
-            if r < stoprev:
-                break
             for pn in self.parents(n):
-                p[pn] = 1
-        return h
+                if pn in reachable:
+                    reachable[n] = 1
+                    heads[n] = 1
+                if pn in heads:
+                    del heads[pn]
+        return heads.keys()
 
     def children(self, node):
         """find the children of a given node"""