diff --git a/mercurial/revset.py b/mercurial/revset.py
--- a/mercurial/revset.py
+++ b/mercurial/revset.py
@@ -192,7 +192,10 @@
         return _orsetlist(repo, subset, xs, order)
 
 def notset(repo, subset, x, order):
-    return subset - getset(repo, subset, x)
+    s = subset - getset(repo, subset, x)
+    if order == defineorder:
+        s.sort()
+    return s
 
 def relationset(repo, subset, x, y, order):
     raise error.ParseError(_("can't use a relation in this context"))
@@ -1138,12 +1141,13 @@
     return baseset(hs)
 
 @predicate('heads(set)', safe=True)
-def heads(repo, subset, x):
+def heads(repo, subset, x, order):
     """Members of set with no children in set.
     """
-    s = getset(repo, subset, x)
-    ps = parents(repo, subset, x)
-    return s - ps
+    s = getset(repo, subset, x, order) - parents(repo, subset, x)
+    if order == defineorder:
+        s.sort()
+    return s
 
 @predicate('hidden()', safe=True)
 def hidden(repo, x):
diff --git a/tests/test-revset-ordering.t b/tests/test-revset-ordering.t
--- a/tests/test-revset-ordering.t
+++ b/tests/test-revset-ordering.t
@@ -46,7 +46,6 @@
   $ check 'E:A'
   $ check 'E % C'
   $ check 'not E'
-  ordering: defineorder not respected
 
   $ check 'adds("*")'
   $ check 'all()'
@@ -70,7 +69,6 @@
   $ check 'grep("A")'
   $ check 'head()'
   $ check 'heads(E+C)'
-  ordering: followorder not respected
   $ check 'merge()'
   $ check 'modifies("A")'
   $ check 'named("tags")'