Priority Queue via Binary Heap — Deep Dive

void push(int val) {
  heap[size] = val;
  int i = size++;
  while (i > 0) {
    int p = (i - 1) / 2;
    if (heap[p] > heap[i]) { swap(p, i); i = p; }
    else break;
  }
}

int pop() {
  int min = heap[0];
  heap[0] = heap[--size];
  int i = 0;
  while (true) {
    int l = 2*i+1, r = 2*i+2, small = i;
    if (l < size && heap[l] < heap[small]) small = l;
    if (r < size && heap[r] < heap[small]) small = r;
    if (small == i) break;
    swap(i, small); i = small;
  }
  return min;
}