The heap structure can be thought to be a binary tree. The heap property states that any parent is smaller than both of its children. This guarantees that the root has the smallest element. In the basic heap, there are insert, delete and peek operations, as in this question. However, there is a slight difference in delete operation. In the basic heap delete, only root is removed. However, this very exercise requires the deletion of a specific value in the heap. Therefore, we must devise a way to find that value by using the heap property. This also makes us to keep the average (not worst) time complexity within the boundries of O(logN).

When an interviewer asked a question like this, most probably we will not be allowed to use data structures provided by the language we are coding with. Rather, we need to implement it from scratch. Let's assume we are using Java and basic arrays. Moreover, we do not know the max operations beforehand.

What we will need are:

1. An identifier to show the last element of the heap, since all capacity of the array may not be filled.
2. A mechanism to put the minimum element to the top of the heap.
3. A search algorithm to find the desired element to delete. This step is crucial.
4. Another mechanism to preserve the heap property after deleting the given element.

The skeleton code below addresses these 4 requirements. int last acts as the boundry identifier, swim() puts the minimum element to the top. findInHeap() searches for the element to be deleted. sink() restores the heap property after deletion. When adding an element, the array can be full. To enlarge it, I add a method, doubleSizeOf() to double the capacity of the heap.

  public static void main(String[] args) {
    int[] heap = new int[16];
    int last = 1;
    Scanner in = new Scanner(System.in);
    int queries = in.nextInt();
    for (int q=0; q<queries; q++) {
      int op = in.nextInt();
      switch (op) {
        case 1:
          int value = in.nextInt();
          if (last == heap.length) {
            heap = doubleSizeOf(heap);
          }
          heap[last] = value;
          swim(heap, last);
          last++;
          break;
        case 2:
          value = in.nextInt();  
          int posToDelete = findInHeap(heap, value, last);
          last--;
          swap(heap, posToDelete, last);
          sink(heap, posToDelete, last);
          swim(heap, posToDelete);
          break;
        case 3:
          if (last > 1) {
            System.out.println(heap[1]); 
          }
          break;
        default:
          ;
      }
    }
    in.close();
  }
  
  private static int[] doubleSizeOf(int[] heap) {
    int [] doubleHeap = new int[heap.length*2];
    for (int i=0; i<heap.length; i++) {
      doubleHeap[i] = heap[i];
    }
    return doubleHeap;
  }

In my implementation, I followed what I remember from Algorithms 4th Edition by Sedgewick. I keep an integer array heap[]and the root of the heap is positioned as heap[1]. Hence the index 0 is never used. This gives us the ability to simply calculate the positions of the left and right children of any parent. Let the parent have an index of i. The left one will have the index of 2*i and the right one will have one more of if, which equals to 2*i+1 When we want to add a new element, we put it as the last element of the array and swim that element upwards the binary tree.

  private static void swim(int[] heap, int pos) {
    int parent = pos/2;
    while (parent>0 && heap[pos]<heap[parent]) {
      swap(heap, parent, pos);
      pos = parent;
      parent = pos/2;
    }
  }
  
  private static void swap(int[] heap, int from, int to) {
    int temp = heap[from];
    heap[from] = heap[to];
    heap[to] = temp;
  }

While going up, we move until the parent is smaller than its new child. If not, we swap the parent and the new child. This can break the heap property so each swap requires one more iteration.

The most critical part is finding the element to be deleted. Since parents are always smaller than the children, we can traverse the tree to find the desired child. However, we cannot use binary search, since there is no strict ordering between the children. Hence, we will first try the left subtree, if it is not there, we must check the right one.

  private static int findInHeap(int[] heap, int key, int last) {
    return findInHeapStartingFrom(heap, key, last, 1);
  }
  
  private static int findInHeapStartingFrom(int[] heap, int key, int last, int pos) {
    if (last <= pos) {
      return -1;
    }
    if (heap[pos] == key) {
      return pos;
    }
    int foundInLeft = findInHeapStartingFrom(heap, key, last, pos*2);
    if (foundInLeft > -1) {
      return foundInLeft;
    }
    return findInHeapStartingFrom(heap, key, last, pos*2+1);
  }

After getting the position of the element, we swap that with the last member of the heap and decrease the indicator by one. Therefore, there may be deleted elements which still linger in the array but cannot be accessed by my implementation. The previously last but now became an internal node element may quite possibly break the heap property. We should either sink it downwards or swim it upwards the binary tree, as proposed by liuzhenchangxc.

  private static void sink(int[] heap, int pos, int last) {
    int left = pos*2;
    int right = pos*2+1;
    int posToSwap = pos;
    if (left<last && heap[left]<heap[posToSwap]) {
      posToSwap = left;
    }
    if (right<last && heap[right]<heap[posToSwap]) {
      posToSwap = right;
    }
    if (pos == posToSwap) {
      return;
    }
    swap(heap, pos, posToSwap);
    sink(heap, posToSwap, last);
  }