python - Heap that supports modification of its elements?


Question: 

Here is my scenario. I want to implement A* (in Python) without having to resort to linear-time min or in operations. I need a heap to be able to efficiently get the lowest weight item.

My immediate response was 'Easy! I'll use heapq!' Then I discovered that life is rarely as simple as we would like it to be. It turns out that this strategy is suboptimal for one of the crucial points of A*. When consider children, I need to occasionally update the scores of the children already on the heap.

For those whose memory of A* has lapse a little, the gist of it is that I want to take an element, modify its weight, and modify the heap to reflect the change, all in sub-linear time.

Any suggestions?




3 Answers: 

For complexity purposes, you would want to try a binomial or Fibonacci heap; it appears that there are implementations of both in Python but not production-grade libraries. A binary or d-ary heap might work faster in practice, though. The heapq page mentions how to do updates (keep a reference to the item that you insert into the heap, mark it as invalid and then insert a new version). There are faster algorithms for maintaining the heap property after updates, though. Look at http://en.wikipedia.org/wiki/D-ary_heap for the algorithms to use for fast updates, but you would probably need to implement your own heap on top of an array for those.

 

It's true, neither the heap functions in heapq nor Queue.PriorityQueue are very functional. It probably takes about equal time to either A: write a rant on your blog or B: implement one yourself.

 

I always end up implementing my own version of a Heap type, for the exact reason that you can't actually search in a Heap, while all efficient methods require "a pointer to the element" as input.

Usually, I implement my Heap as a combination of an unstructured container of Items, and a Heap of pointers (or indeces) to Items. If you keep a pointer to a Heap location in the Item, you have an immediate two-way link: a) Given a Heap element (e.g. returned by extractMin, or during a comparison): dereference the pointer, and you've got your item. b) Given an Item (e.g. through an adjacency list of a Graph algorithm): pass the pointer to whatever update function you want.

Of course, this causes space overhead (2 additional pointers/integers per Item), but it makes Heap restructuring very cheap (swapping a few pointers instead of swapping entire Items), which in return makes it less painful to add some additional satellite data to your Items.

 

More Articles


java - log4j directs all log output to stdout even though it's not supposed to

In my log4j.properties I have:log4j.rootLogger=DEBUG,stdoutlog4j.logger.notRootLogger=DEBUG,somewhereelseThe appenders stdout and somewhereelse are both configured properly, stdout writes to the console and somewhereelse writes to a file.In my code in each class either I set either:static Logger log

clone a git repository with SSH and libgit2sharp

I'm trying to use the library "libgit2sharp" to clone a repository via a SSH key and... I can't find anything... I can clone it via "https" but what I'd like to do is using an SSH key. It's really unclear if it is supported or not.

Split String With Numbers in R

This question already has an answer here: Split a string by any number of spaces 2 answers


Access remote git repo via ssh, using libgit2sharp

I'm trying to get a simple working example for cloning or accessing a remote git repository via ssh. After adding nuget package LibGit2Sharp-SSH v1.0.22, got a .Net Framework v4.6.1 console application like this:using LibGit2Sharp;using System;using System.IO;class Program{ static void Main(strin

javascript - onDelete not being called when deleting a node in Cloud Functions for Firebase

I am trying to build triggers for a firebase app around following and followers. Below is a snippet of my cloud code. I want to increase a counter when a user follows. For this I use oncreate (for when the user gains their first follower due the structure not existing until this point) and then I

java - Location mocking - google map detects the movement but my own application not triggering location change

I am facing a strange issue. I modified official mock provider source code provided by google to mock some route for my application.Using this code. mockLocation.setElapsedRealtimeNanos(elapsedTimeNanos); mockLocation.setTime(currentTime); // Set the loc


android - Can't find class [org/drinkless/td/libcore/telegram/TdApi$Object]

I am getting this error "Can't find class [org/drinkless/td/libcore/telegram/TdApi$Object]" but I haven't used this class anywhere in my project.I haven't used that class anywhere.But i am getting the above errorCan anyone please let me know how to solve the above error.

How do I cross-compile a Linux kernel to a MIPS little endian host?

The kernel in question is 2.6.18. If I callmake ARCH=mips CROSS_COMPILE=mipsel-linux- menuconfigthere will be only the option to build a big endian kernel in the menu. If I use ARCH=mipsel, it will complain about not having an arch/mipsel dir.How's this done?

php - Key for HMAC Algorithm

How to generate the secret key for the HMAC algorithm as I have to use it for data verification at the other clients end?Thanks in advance.

android - Why getLastKnownLocation(provider) doesn't return null after clearTestProviderLocation(provider)

I was assuming that getLastKnownLocation does return null for a given provider after calling clearTestProviderLocation for same provider.Why ? because documentation says for clearTestProviderLocation; Removes any mock location associated with the given provider.public void test() throws SecurityExc