What is the most effective way to find the node with the lowest value to expand in A star with heuristic?

im doing the 8 puzzle solver with the a st开发者_如何学Goar algorithm. I implement Manhattan and misplaced heuristic functions in this solver. In some cases, the solver works fine. But in some cases, it takes a lot of time to find the solution. I think that one of my problem is in the function that looks for the node with the lowest value in the open list(waiting for expansion).

 a part of psedocode(from wiki)
 while openset is not empty
     x := the node in openset having the lowest f_score[] value
     if x = goal
         return reconstruct_path(came_from, came_from[goal])
     ................................

So what is the best way to find the lowest f_score value? Just find the minimum value, or we have to modify the list when we have a state to add( sort the list when we add the state) so the minimum value will be in the first position.

Maintain a heap.

Given n elements you can turn them into a heap in time O(n). Once they are a heap you can add and remove elements in time O(log(n)) and you can find the smallest element in time O(1).

To implement one all that you need is an array. The root node is 0 and the nodes below the i'th are at 2*i+1 and 2*i + 2. The heap condition is that every node is smaller than the nodes above it. The smallest is always the root. To add an element, just push it onto the array, and let it "fall down" to its natural level. To remove an element take the root element out, take the last element off the array, put it at the root, and let it "bubble up" to the right place. (In the "bubbling up" phase you swap it with the smaller of its two child nodes until it finally doesn't have smaller child nodes below it.) To efficiently create an array you start at the median element and let each element "bubble up". This operation looks like O(n log(n)) but a careful analysis shows that it is only O(n).