In A* search, which data structure would be more efficient ? Min-heap or Binary search tree.
Considering that below operations are to be handled frequently:
(a) extract min
(b) search a node
(c) update the node
(d) insert a node
Note: Search operation would be very frequent as we need to check the presence of each probable child node in the open-list of A*.
A min-heap is a much simpler data structure than a balanced binary search tree, and it's typically implemented in an array, which reduces memory used and improves cache locality.
For these reasons, a min-heap implementation will be much faster if you do it right.
It's often tricky to implement the decrease-key operation in an array-based min-heap, though.  The usual solution is not to implement decrease-key at all, but just to insert another record in the min-heap whenever the distance to a node is decreased.
This will not increase the time complexity of the algorithm, the min-heap will take O(|E|) space.  If your graph is very dense, then a node's weight may be decreased many times, and this memory consumption might be too much.  If that's so, then you should just clean up the min-heap -- remove invalid entries and re-heapify -- whenever more than half of the entries in the heap are invalid.  This will keep memory consumption down to O(|V|) without significantly affecting run time.
Which data structure is more efficient for A*?