redef fun take
	do
		var res = peek
		peek_cached = false
		seq.remove(res)
		return res
	end

	redef fun take do
		#assert assert_best else print "tri to take"
		#var ol = length
		if length < 2 then return items.pop

		var res = items.first
		var ei = 1
		var e = items.pop

		var last = items.length
		loop
			# Check first child
			var ci = ei*2
			if ci > last then break # no children
			var c = items[ci-1]
			var upc = comparator.compare(e, c) > 0

			# Check second child
			var c2i = ci + 1
			if c2i <= last then do
				var c2 = items[c2i-1]
				# possibility to bubble-down to c2, or not?
				if comparator.compare(e, c2) <= 0 then break label
				# c2 is a better path, or not?
				if upc and comparator.compare(c2, c) > 0 then break label
				# goes to c2 path
				upc = true
				c = c2
				ci = c2i
			end label

			# bubble-down?
			if not upc then break

			items[ei-1] = c
			ei = ci
		end
		items[ei-1] = e
		#assert length == ol - 1 else print "is {length}, expected {ol - 1}"
		#assert assert_best else print "dequed {res}"
		return res
	end

	redef fun take do return seq.pop

	redef fun take do return seq.shift