Sorry for the wrong answer. I think this is how its done.The random node deletion will take O(n)+O(log(n)).
At first I need to search for the node in the heap(O(n)) then I can exchange the element with the last element.
After exchange we can delete the last element and decrease the heap size by 1. Then I can apply max/min Heapify at the earlier position of the where the value was present which will take O(log n).
Please refer : https://gateoverflow.in/273601/made-easy-test-series