Interesting remark. So, a "data structure where the largest remaining element can be extracted in O(1) time" can be turned into a sorted list in O(n) time. So,

Interesting remark. So, a "data structure where the largest remaining element can be extracted in O(1) time" can be turned into a sorted list in O(n) time. So, under the assumtions, the overall algorithm does complete in constant time.