What do I use for a max-heap implementation in Python

Question

Python includes the heapq module for min-heaps  but I need a max heap   What should I use for a max-heap implementation in Python

User · Answer

The easiest way is to invert the value of the keys and use heapq   For example  turn 1000 0 into -1000 0 and 5 0 into -5 0

User · Answer

Following up to Isaac Turner s excellent answer  I d like put an example based on K Closest Points to the Origin using max heap   from math import sqrt import heapq   class MaxHeapObj object       def   init   self  val           self val   val distance         self coordinates   val coordinates      def   lt   self  other           return self val  gt  other val      def   eq   self  other           return self val    other val      def   str   self           return str self val    class MinHeap object       def   init   self           self h           def heappush self  x           heapq heappush self h  x       def heappop self           return heapq heappop self h       def   getitem   self  i           return self h i       def   len   self           return len self h    class MaxHeap MinHeap       def heappush self  x           heapq heappush self h  MaxHeapObj x        def heappop self           return heapq heappop self h  val      def peek self           return heapq nsmallest 1  self h  0  val      def   getitem   self  i           return self h i  val   class Point        def   init   self  x  y           self distance   round sqrt x  2   y  2   3          self coordinates    x  y    def find k closest points  k       res    Point x  y  for  x  y  in points      maxh   MaxHeap        for i in range k           maxh heappush res i        for p in res k            if p distance  lt  maxh peek                maxh heappop               maxh heappush p       res    str x coordinates  for x in maxh h      print f  k  closest points from origin         join res       points     10  8    -2  4    0  -2    -1  0    3  5    -2  3    3  2    0  1   find k closest points  3

User · Answer

The solution is to negate your values when you store them in the heap  or invert your object comparison like so  import heapq  class MaxHeapObj object     def   init   self  val   self val   val   def   lt   self  other   return self val  gt  other val   def   eq   self  other   return self val    other val   def   str   self   return str self val   Example of a max-heap  maxh      heapq heappush maxh  MaxHeapObj x   x   maxh 0  val    fetch max value x   heapq heappop maxh  val    pop max value  But you have to remember to wrap and unwrap your values  which requires knowing if you are dealing with a min- or max-heap  MinHeap  MaxHeap classes Adding classes for MinHeap and MaxHeap objects can simplify your code  class MinHeap object     def   init   self   self h        def heappush self  x   heapq heappush self h  x    def heappop self   return heapq heappop self h    def   getitem   self  i   return self h i    def   len   self   return len self h   class MaxHeap MinHeap     def heappush self  x   heapq heappush self h  MaxHeapObj x     def heappop self   return heapq heappop self h  val   def   getitem   self  i   return self h i  val  Example usage  minh   MinHeap   maxh   MaxHeap     add some values minh heappush 12  maxh heappush 12  minh heappush 4  maxh heappush 4    fetch  quot top quot  values print minh 0   maxh 0       quot 4 12 quot    fetch and remove  quot top quot  values print minh heappop    maxh heappop        quot 4 12 quot

User · Answer

Extending the int class and overriding   lt   is one of the ways   import queue class MyInt int       def   lt   self  other           return self  gt  other  def main        q   queue PriorityQueue       q put MyInt 10       q put MyInt 5       q put MyInt 1       while not q empty            print  q get      if   name         main         main

User · Answer

This is a simple MaxHeap implementation based on heapq  Though it only works with numeric values   import heapq from typing import List   class MaxHeap      def   init   self           self data           def top self           return -self data 0       def push self  val           heapq heappush self data  -val       def pop self           return -heapq heappop self data    Usage   max heap   MaxHeap   max heap push 3  max heap push 5  max heap push 1  print max heap top       5

User · Answer

You can use   import heapq listForTree    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15      heapq heapify listForTree                for a min heap heapq  heapify max listForTree           for a maxheap     If you then want to pop elements  use   heapq heappop minheap         pop from minheap heapq  heappop max maxheap    pop from maxheap

User · Answer

I have created a heap wrapper that inverts the values to create a max-heap  as well as a wrapper class for a min-heap to make the library more OOP-like  Here is the gist  There are three classes  Heap  abstract class   HeapMin  and HeapMax    Methods   isempty   - gt  bool  obvious getroot   - gt  int  returns min max push   - gt  None  equivalent to heapq heappush pop   - gt  int  equivalent to heapq heappop view min   view max   - gt  int  alias for getroot   pushpop   - gt  int  equivalent to heapq pushpop

User · Answer

If you are inserting keys that are comparable but not int-like  you could potentially override the comparison operators on them  i e   lt   become   and   becomes  lt     Otherwise  you can override heapq  siftup in the heapq module  it s all just Python code  in the end

User · Answer

class MaxHeap       def   init   self  items              self heap    0          self items   items         for item in items              self heap append item              self   floatUp len self heap -1        quot  quot  quot       self heap    0  heap index stars form 1     self heap append item  append items from list to heap     append items to it s proper place      quot  quot  quot       def push self  data           self heap append data          self   floatUp len self heap -1                quot  quot  quot      Append data to the end of the list the using float up put it to the proper place      quot  quot  quot        def peek self           if self heap 1               return self heap 1          else              return False                             quot  quot  quot      To return the first element form list      quot  quot  quot       def pop self           if  len self heap    gt  2              self   swap 1 len self heap -1              max   self heap pop               self   bubbleDown 1           elif  len self heap      2              max   self heap pop           else              return False         return max           quot  quot  quot      If length is greater than two then swap first and last value as only the last value can be removed from the tree     Place the new first item after removing of the item to its proper place using bubble down      quot  quot  quot                def   swap self  i  j           self heap i   self heap j    self heap j   self heap i        quot  quot  quot      Swap is used in a bubble down and bubble up for proper placing of values is list      quot  quot  quot           def   floatUp self  index           parent   index    2         if index  lt   1              return         elif self heap index   gt  self heap parent               self   swap index  parent              self   floatUp parent            quot  quot  quot      if value and parents   where parent  lt  value   swap where parent  value   value parent     After swap again check parent  gt  value    True if false then again continue      quot  quot  quot       def   bubbleDown self  index           left   index   2         right   index   2   1         largest   index          if len self heap   gt  left and self heap largest   lt  self heap left               largest   left          if len self heap   gt  right and self heap largest   lt  self heap right               largest   right          if largest    index              self   swap index  largest              self   bubbleDown largest       quot  quot  quot      self heap largest   lt  self heap left    largest   left     current value and lower left value is bigger largest   left     self heap largest   gt  self heap right      current value and lower value right value if lower right value is bigger than largest value          after getting the largest value we will swap larger value and smaller value and them again check that the current value is      bigger than is down value then again swap space and check again until every node is settled at its the correct place       quot  quot  quot           def   str   self           return str self heap            quot  quot  quot      To str representation of the list      quot  quot  quot   m   MaxHeap  95  3  21    m push 10   print m   print m pop     print m peek

User · Answer

I implemented a max heap version of heapq and submitted it to PyPI    Very slight change of heapq module CPython code    https   pypi python org pypi heapq max   https   github com he-zhe heapq max  Installation  pip install heapq max   Usage  tl dr  same as heapq module except adding     max    to all functions   heap max                                  creates an empty heap heappush max heap max  item               pushes a new item on the heap item   heappop max heap max               pops the largest item from the heap item   heap max 0                         largest item on the heap without popping it heapify max x                             transforms list into a heap  in-place  in linear time item   heapreplace max heap max  item     pops and returns largest item  and                                       adds new item  the heap size is unchanged

User · Answer

The easiest and ideal solution     Multiply the values by -1   There you go  All the highest numbers are now the lowest and vice versa   Just remember that when you pop an element to multiply it with -1 in order to get the original value again

User · Answer

Allowing you to chose an arbitrary amount of largest or smallest items  import heapq heap    23  7  -4  18  23  42  37  2  8  2  23  7  -4  18  23  42  37  2  heapq heapify heap  print heapq nlargest 3  heap       42  42  37  print heapq nsmallest 3  heap      -4  -4  2

User · Answer

To elaborate on https   stackoverflow com a 59311063 1328979  here is a fully documented  annotated and tested Python 3 implementation for the general case   from   future   import annotations    To allow  MinHeap push - gt  MinHeap   from typing import Generic  List  Optional  TypeVar from heapq import heapify  heappop  heappush  heapreplace   T   TypeVar  T     class MinHeap Generic T                MinHeap provides a nicer API around heapq s functionality      As it is a minimum heap  the first element of the heap is always the     smallest       gt  gt  gt  h   MinHeap  3  1  4  2        gt  gt  gt  h 0      1      gt  gt  gt  h peek       1      gt  gt  gt  h push 5     N B   the array isn t always fully sorted       1  2  4  3  5       gt  gt  gt  h pop       1      gt  gt  gt  h pop       2      gt  gt  gt  h pop       3      gt  gt  gt  h push 3  push 2       2  3  4  5       gt  gt  gt  h replace 1      2      gt  gt  gt  h      1  3  4  5              def   init   self  array  Optional List T     None           if array is None              array              heapify array          self h   array     def push self  x  T  - gt  MinHeap          heappush self h  x          return self    To allow chaining operations      def peek self  - gt  T          return self h 0      def pop self  - gt  T          return heappop self h      def replace self  x  T  - gt  T          return heapreplace self h  x      def   getitem   self  i  - gt  T          return self h i      def   len   self  - gt  int          return len self h      def   str   self  - gt  str          return str self h      def   repr   self  - gt  str          return str self h    class Reverse Generic T                Wrap around the provided object  reversing the comparison operators       gt  gt  gt  1  lt  2     True      gt  gt  gt  Reverse 1   lt  Reverse 2      False      gt  gt  gt  Reverse 2   lt  Reverse 1      True      gt  gt  gt  Reverse 1   lt   Reverse 2      False      gt  gt  gt  Reverse 2   lt   Reverse 1      True      gt  gt  gt  Reverse 2   lt   Reverse 2      True      gt  gt  gt  Reverse 1     Reverse 1      True      gt  gt  gt  Reverse 2   gt  Reverse 1      False      gt  gt  gt  Reverse 1   gt  Reverse 2      True      gt  gt  gt  Reverse 2   gt   Reverse 1      False      gt  gt  gt  Reverse 1   gt   Reverse 2      True      gt  gt  gt  Reverse 1      1             def   init   self  x  T  - gt  None          self x   x     def   lt   self  other  Reverse  - gt  bool          return other x   lt   self x      def   le   self  other  Reverse  - gt  bool          return other x   le   self x      def   eq   self  other  - gt  bool          return self x    other x     def   ne   self  other  Reverse  - gt  bool          return other x   ne   self x      def   ge   self  other  Reverse  - gt  bool          return other x   ge   self x      def   gt   self  other  Reverse  - gt  bool          return other x   gt   self x      def   str   self           return str self x      def   repr   self           return str self x    class MaxHeap MinHeap               MaxHeap provides an implement of a maximum-heap  as heapq does not provide     it  As it is a maximum heap  the first element of the heap is always the     largest  It achieves this by wrapping around elements with Reverse      which reverses the comparison operations used by heapq       gt  gt  gt  h   MaxHeap  3  1  4  2        gt  gt  gt  h 0      4      gt  gt  gt  h peek       4      gt  gt  gt  h push 5     N B   the array isn t always fully sorted       5  4  3  1  2       gt  gt  gt  h pop       5      gt  gt  gt  h pop       4      gt  gt  gt  h pop       3      gt  gt  gt  h pop       2      gt  gt  gt  h push 3  push 2  push 4       4  3  2  1       gt  gt  gt  h replace 1      4      gt  gt  gt  h      3  1  2  1              def   init   self  array  Optional List T     None           if array is not None              array    Reverse x  for x in array     Wrap with Reverse          super     init   array      def push self  x  T  - gt  MaxHeap          super   push Reverse x           return self     def peek self  - gt  T          return super   peek   x     def pop self  - gt  T          return super   pop   x     def replace self  x  T  - gt  T          return super   replace Reverse x   x   if   name         main         import doctest     doctest testmod     https   gist github com marccarre 577a55850998da02af3d4b7b98152cf4

User · Answer

In case if you would like to get the largest K element using max heap  you can do the following trick   nums   3 2 1 5 6 4  k   2   k being the kth largest element you want to get heapq heapify nums   temp   heapq nlargest k  nums  return temp -1

[python] What do I use for a max-heap implementation in Python?

Examples related to python

Examples related to data-structures

Examples related to heap

Examples related to recursive-datastructures