How to update elements within a heap? (priority queue)
Typical Solution
The usual solution is to mark an element as invalid and insert a new element, then eliminate the invalid entries as they are popped-off.
Alternative Solution
If that approach doesn't suffice, it is possible restore the min-heap invariant in O(log n) steps as long as the location of the value being changed is known.
Recall that min-heaps are built and maintained using two primitives, "siftup" and "siftdown" (though various sources have differing opinions on which is up and which is down). One of those pushes values down the tree and the other floats them upward.
Case 1: Value is increased
If the new value x1 is greater than the old value x0, then only the tree under x needs to be fixed because parent(x) <= x0 < x1
. Just push x down the tree by swapping x with the smaller of its two children while x is bigger than one of its children.
Case 2: Value is decreased
If the new value x1 is less than the old value x, the tree below x needs no adjustment because x1 < x0 <= either_child(x)
. Instead, we just need to move upward, swapping x with its parent while x is less than its parent. Sibling nodes need not be considered because they are already greater than or equal to a parent which will potentially be replaced with a lower value.
Case 3: Value is unchanged
No work is necessary. The existing invariants are unchanged.
Working code in Python
Test 1,000,000 trials: Create a random heap. Alter a randomly selected value. Restore the heap condition. Verify that the result is a min-heap.
from heapq import _siftup, _siftdown, heapify
from random import random, randrange, choice
def is_minheap(arr):
return all(arr[i] >= arr[(i-1)//2] for i in range(1, len(arr)))
n = 40
trials = 1_000_000
for _ in range(trials):
# Create a random heap
data = [random() for i in range(n)]
heapify(data)
# Randomly alter a heap element
i = randrange(n)
x0 = data[i]
x1 = data[i] = choice(data)
# Restore the heap
if x1 > x0: # value is increased
_siftup(data, i)
elif x1 < x0: # value is decreased
_siftdown(data, 0, i)
# Verify the results
assert is_minheap(data), direction
Updateable Priority Queue
Binary heaps (which are how priority queues are implemented in the C++ standard library) do not support arbitrary update-key operations. A common method if updates are infrequent is to extrinsically flag the original item as invalid, and reinsert the value with the new key; when an invalid value is popped, it is ignored.
The alternative is using a different PQ implementation which does support update-key, such as a binomial heap. Binomial heaps have the particular advantage of being manipulated by swinging pointers, instead of moving values. This streamlines the task of implementing operations like update-key and delete.
How can I sort function using priority queue in C++/C?
std::priority_queue works with a compare function which can't work with the given functions. You need to define your own priorities as an enum and then you can put the pair of the prio and function in an std::multimap so all functions can be called according to their prio. You can put the pair also in a prio-q but then you still need a compare function that only works on the prio.
e.g.:
#include <iostream>
#include <map>
#include <functional>
enum class prio { HI, MID, LO };
int main()
{
std::multimap<prio, std::function<void()>> prio_mmap;
prio_mmap.insert(std::make_pair(prio::MID, []{ std::cout << "MID1\n"; }));
prio_mmap.insert(std::make_pair(prio::LO, []{ std::cout << "LO\n"; }));
prio_mmap.insert(std::make_pair(prio::HI, []{ std::cout << "HI\n"; }));
prio_mmap.insert(std::make_pair(prio::MID, []{ std::cout << "MID2\n"; }));
for (const auto& p: prio_mmap)
{
p.second();
}
}
Implementing a PriorityQueue Algorithm
The main issue is that the parent
function is wrong. As it should do the opposite from the left
and right
methods, you should first subtract 1 from i
before halving that value:
def parent(self, i):
return int((i-1)/2)
Other things to note:
You don't really have a good use for the member
self.min_index
. It is either 0 orNone
, and the difference is not really used in your code, as it follows directly from whether the heap is empty or not. This also means you don't need the method_find_min
, (which in itself is strange: you assign tomin
, but never use that). Any way, drop that method, and the line where you call it. Also drop the line where you assignNone
toself.min_index
, and the only other place where you read the value, just use 0.You have two ways to protect against index errors in the
min_heapify
method:<= heapsize
and atry
block. The first protection should really have<
instead of<=
, but you should use only one way, not two. So either test the less-than, or trap the exception.The
else
block withsmallest = i
is unnecessary, because at that timesmallest == i
.min_heapify
has a first parameter that always receives the full size of the heap. So it is an unnecessary parameter. It would also not make sense to ever call this method with another value for it. So drop that argument from the method definition and all calls. And then defineheap_size = len(self.queue)
as a local name in that functionIn
heap_decrease_key
you commented out the assignment#self.queue[i] = key
, which is fine as long as you never call this method to really decrease a key. But although you never do that from "inside" the class, the user of the class may well want to use it in that way (since that is what the method's name is suggesting). So better uncomment that assignment.With the above changes, your instance would only have
queue
as its data property. This is fine, but you could consider to letPriorityQueue
inherit fromlist
, so that you don't need this property either, and can just work with the list that you inherit. By consequence, you should then replaceself.queue
withself
throughout your code, and you can drop the__init__
and__len__
methods, since thelist
implementation of those is just what you need. A bit of care is needed in the case where you want to call alist
original method, when you have overridden it, likeappend
. In that case usesuper().append
.
With all of the above changes applied:
class PriorityQueue(list):
"""Array-based priority queue implementation."""
def parent(self, i):
return int((i-1)/2)
def left(self, i):
return 2*i+1
def right(self, i):
return 2*i+2
def min_heapify(self, i):
#Min heapify as written in CLRS
heap_size = len(self)
smallest = i
l = self.left(i)
r = self.right(i)
if l < heap_size and self[l] < self[i]:
smallest = l
if r < heap_size and self[r] < self[smallest]:
smallest = r
if smallest != i:
self[i], self[smallest] = self[smallest], self[i]
self.min_heapify(smallest)
def heap_decrease_key(self, i, key):
#Implemented as specified in CLRS
if key > self[i]:
raise ValueError("new key is larger than current key")
self[i] = key
while i > 0 and self[self.parent(i)] > self[i]:
self[i], self[self.parent(i)] = self[self.parent(i)], self[i]
i = self.parent(i)
def append(self, key):
"""Inserts an element in the priority queue."""
if key is None:
raise ValueError('Cannot insert None in the queue')
super().append(key)
heap_size = len(self)
self.heap_decrease_key(heap_size - 1, key)
def min(self):
"""The smallest element in the queue."""
if len(self) == 0:
return None
return self[0]
def pop(self):
"""Removes the minimum element in the queue.
Returns:
The value of the removed element.
"""
if len(self) == 0:
return None
popped_key = self[0]
self[0] = self[-1]
del self[-1]
self.min_heapify(0)
return popped_key
Related Topics
Where Are Member Functions Stored for an Object
What Are Good Practices Regarding Shared Libraries on Linux
Setjmp/Longjmp: Why Is This Throwing a Segfault
How to Find Out If a Tuple Contains a Type
Do These Members Have Unspecified Ordering
Detect Gcc Compile-Time Flags of a Binary
How to Use a C++ Smart Pointers Together with C's Malloc
How to Declare Variables of Different Types in the Initialization of a for Loop
How to Enable Experimental C++11 Concurrency Features in Mingw
If Temporaries Are Implicitly Non-Modifiable, How Does This Work
How to Securely Disconnect an Asio Ssl Socket
Why "Initializer-String for Array of Chars Is Too Long" Compiles Fine in C & Not in C++
How to Typedef a Function Pointer with the C++11 Using Syntax
Do All Virtual Functions Need to Be Implemented in Derived Classes
How to Build Google's Protobuf in Windows Using Mingw
How to Solve -------Undefined Reference to '_Chkstk_Ms'-------On Mingw