Search an element in a heap

As mentioned by others, search in a PriorityQueue is linear, as it has no notion of where to look for a particular key other than the root of the heap. This is the main difference from a BST, where you always know to go either left or right depending on the value you are searching. In a heap, the smallest is always at the root, and the child can be on either the left or right subtree.

However, you can modify the PriorityQueue to keep an additional index array which maps an index k to its location in the heap array. This will allow the following operations:

void insert(int k, Item item) : insert item and associate it with k, so that you can later access it directly by by k

Item get(k) : return the item associated with index k. This could be anywhere in the heap.

void change(int k, Item item) : change the item associated with k to item. This will require a "reheapify" to ensure the heap order is maintained.

The implementation is somewhat tricky as you need to ensure the heap and index array are always in sync and pointing to the correct object. If you already know how to implement a regular heap, try adding the index array and see what needs to change to maintain the correct order. Here's a full implementation https://algs4.cs.princeton.edu/24pq/IndexMinPQ.java.html

You need to search through every element in the heap in order to determine if an element is inside.

One optimization is possible, though (we assume a max heap here). If you have reached a node with a lower value than the element you are searching for, you don't need to search further from that node. However, even with this optimization, search is still O(N) (need to check N/2 nodes in average).