heapq with custom compare predicate

by

According to the heapq documentation, the way to customize the heap order is to have each element on the heap to be a tuple, with the first tuple element being one that accepts normal Python comparisons.

The functions in the heapq module are a bit cumbersome (since they are not object-oriented), and always require our heap object (a heapified list) to be explicitly passed as the first parameter. We can kill two birds with one stone by creating a very simple wrapper class that will allow us to specify a key function, and present the heap as an object.

The class below keeps an internal list, where each element is a tuple, the first member of which is a key, calculated at element insertion time using the key parameter, passed at Heap instantiation:

# -*- coding: utf-8 -*-
import heapq

class MyHeap(object):
   def __init__(self, initial=None, key=lambda x:x):
       self.key = key
       self.index = 0
       if initial:
           self._data = [(key(item), i, item) for i, item in enumerate(initial)]
           self.index = len(self._data)
           heapq.heapify(self._data)
       else:
           self._data = []

   def push(self, item):
       heapq.heappush(self._data, (self.key(item), self.index, item))
       self.index += 1

   def pop(self):
       return heapq.heappop(self._data)[2]

(The extra self.index part is to avoid clashes when the evaluated key value is a draw and the stored value is not directly comparable – otherwise heapq could fail with TypeError)

More Related Contents:

  1. How do I sort a dictionary by value?
  2. How do I sort a list of dictionaries by a value of the dictionary?
  3. How to keep keys/values in same order as declared?
  4. How can I sort a dictionary by key?
  5. Pythonic way to check if a list is sorted or not
  6. About Python’s built in sort() method
  7. Quicksort with Python
  8. Sorting text file by using Python
  9. Why is Bubble Sort implementation looping forever?
  10. How to sort objects by multiple keys?
  11. Sorting a dictionary by value then key
  12. How does the key argument in python’s sorted function work?
  13. How do I sort a dictionary by key?
  14. Destructuring-bind dictionary contents
  15. Sorting a dictionary with lists as values, according to an element from the list
  16. Sort nested dictionary by value, and remainder by another value, in Python
  17. In Python, how do I iterate over a dictionary in sorted key order?
  18. How to sort IP addresses stored in dictionary in Python?
  19. Find elements of array one nearest to elements of array two
  20. What is the complexity of the sorted() function?
  21. How to sort dictionary by key in numerical order Python
  22. What algorithm does Python’s built-in sort() method use?
  23. Right way to initialize an OrderedDict using its constructor such that it retains order of initial data?
  24. Sort a list of tuples by second value, reverse=True and then by key, reverse=False
  25. sorting list of nested dictionaries in python
  26. How to sort a list of dictionaries by a value of the dictionary in Python?
  27. Mergesort with Python
  28. What is this odd sorting algorithm?
  29. Python: Using vars() to assign a string to a variable
  30. Python – sum values in dictionary

Leave a Comment