So first thing: this structure was designed to be an efficient priority queue, not search structure so find operation is O(n)
. Normally you know exact node you want to change. Let's look on an example - Dijkstra's algorithm.
In every step you push graph vertex to the heap or change its priority so it's natural to hold pointer to the heap node in vertex. This way it works great!
So basically you will store the pointer to a node somewhere (you can store them in a hashmap or AVL tree).