Hi,

The attached patch adds a 'key' optional parameter to the heapq.merge function that behaves as in sorted().

Related discussion: http://mail.python.org/pipermail/python-ideas/2012-January/013295.html

This is my first contribution to CPython.

The attached script benchmarks the basline (current implementation) against 3 new implementations, as suggested on http://mail.python.org/pipermail/python-ideas/2012-January/013296.html

On my machine, the output is:

    merge_baseline
    per run, min of 3 = 7.527 ms
    
    merge_1
    per run, min of 3 = 9.894 ms
    131.449 % of baseline
    
    merge_2
    per run, min of 3 = 7.948 ms
    105.594 % of baseline
    
    merge_3
    per run, min of 3 = 7.581 ms
    100.716 % of baseline

On this particular input, merge_2 adds 6% of overhead when the key parameter is not used. While merge_3 only adds 1% of overhead, it almost doubles the amount of code. (Which was admittedly not that long to begin with.)

The patch in the previous message is with the merge_2 implementation, which seemed like the best compromise to me.

Oops, the patch to the documentation would also need 'New in 3.3: the key parameter', with the right Sphinx directive. But that depends on whether this change ends up in 3.3 or 3.4.

Does 3.3 still get new features?

Yes, 3.3 is still in the early development stage, and new features will be accepted until the first beta (in June, see PEP 398).  “.. versionadded:: 3.3 The *key* parameter” will do.

Simon, please keep the original version fast by creating two code paths:

   if key is None:
      original_code
   else:
      new_code using the key_function

Raymond, please have a look at merge_3 in benchmark_heapq_merge.py. It is implemented as you say.

Do you think the speed is worth the code duplication?

heapq_merge_key_duplicate.patch is a new patch with two code path. It also updates the function’s docstring (which the previous patch did not). Raymond, do you think the speed is worth the DRY violation?

I'll look at this in the next couple of weeks.  Hang tight :-)

FWIW, Guido approves of the idea, msg152969 in #4356

I just remembered about this. I suppose it is too late for 3.3?

Yes, 3.3 is already in beta.

Attaching a rough draft implementation for a fully encapsulated Heap() class that is thread-safe, supports minheaps and maxheaps, and efficiently implements key-functions (called no more than once per key).

heap2.diff contains only a single line's change.  Wrong file attached?

Ah, I see the new file now (I'd failed to refresh my browser);  sorry for the noise.

Looks pretty good to me.

- There's a bonus print call in the diff.

- Should the "len(self._data)" call be protected by the lock?  I can't immediately think of any reason why that would be necessary (e.g., pushpop nd poppush never change the size of self._data, so there's no risk of getting a bogus length there), but the lack of the lock makes me nervous.

- Support for iter() seems a bit out of place to me.  What are the use-cases for this?  Would it make sense to leave this out (for now)?

There is already one heap class in the stdlib: queue.PriorityQueue. Why create a duplicate instead extend queue.PriorityQueue with desired features?

May be name the maxheap parameter as reverse?