Python PriorityQueue Heapify Method

Question

I am using this library for a heap:

from Queue import PriorityQueue

I need to trigger a heapify because in this priority queue i am inserting a node class and the prioirty queue is ordered based on node.val like this:

class Node():
   __init__(self,val,text):
       self.val = val
       self.text = text

and my pq:

pq = PriorityQueue()
first = Node(1,'abcd')
pq.put((first.val,first))

xyz = Node(10,'asdf')
pq.put((xyz.val,xyz))


fsa = Node(7,'asdsbcd')
pq.put((fsa.val,fsa))

now it works fine but if i want to for example change first nodes value like this:

first.val = 100

is there a method like pq.heapify() or something..

how do i call a heapify method so that it can sort it? because if i dont then it will be sort the list and assume first still is 1 not 100.

Answer 1

I believe it would be better to use heapq library for your heap.

Then you can use a process from this answer to update the min value in the heap as follows.

Advantages:

1. Approach allows updating smallest element using replace.
2. Takes only O(log(n)) to update the value of the smallest element (i.e. changing first from 1 to 100)
3. Faster than using Heapify when only one item needs to be updated (which takes O(n))

Code

import heapq

class Node():
  def __init__(self,val,text):
       self.val = val 
       self.text = text
  def __str__(self):   # Add a method to node to string for display
    return f'{self.val}, {self.text}'

class MyHeap(object):
  """The class keeps an internal list, where each element is a tuple.
    The first tuple element is the priority (val), calculated at element insertion 
    time, using the key parameter, passed at Heap instantiation"""
  def __init__(self, initial=None, key=lambda x:x.val):
    self.key = key
    if initial:
      self._data = [(key(item), item) for item in initial]
      heapq.heapify(self._data)
    else:
      self._data = []

  def push(self, item):
    heapq.heappush(self._data, (self.key(item), item))

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

  def replace(self, item):
    # Pops min element and adds a new element
    v = self.pop()
    self.push(item)
    return v

Testing

Test 1. Add Elements and dump heap

# Add elements
pq = MyHeap()
first = Node(1,'abcd')
pq.push(first)

xyz = Node(10,'asdf')
pq.push(xyz)

fsa = Node(7,'asdsbcd')
pq.push(fsa)

# Dump elements in order
print('Initial Ordering')
while pq._data:
  print(pq.pop())

Result

Initial Ordering
1, abcd
7, asdsbcd
10, asdf

Test 2. Remove smallest and add as new element with larger value with new value

# Add elements
pq.push(first)
pq.push(xyz)
pq.push(fsa)

# Update first element using replace
first.val = 100
pq.replace(first)

print('\nNew Ordering')
while pq._data:
  print(pq.pop())

Result

New Ordering
7, asdsbcd
10, asdf
100, abcd

Test 3: Add Elements as List

print('\nUsing List')
pq = MyHeap([first, xyz, fsa])
while pq._data:
  print(pq.pop())

Result

Using List
7, asdsbcd
10, asdf
100, abcd