Priority Queues

A priority queue is a data structure for maintaining a set of elements, each with an associated value called a key. Like heaps, they have two variants, $min$ and $max$. A max-priority queue supports the following operations:

• $INSERT(S,\; x,\; k)$: inserts the element $x$ with key $k$ into $S$
• $MAXIMUM(S)$: returns the element from $S$ with the largest key
• $EXTRACT-MAX(S)$: returns and removes the element from $S$ with the largest key
• $INCREASE-KEY(S,\; x,\; k)$: increases the value of $x$'s key to $k$ (assumes $x$'s previous key was less than or equal to $k$)

Whereas a min-priority queue would have equivalent $INSERT$, $MINIMUM$, $EXTRACT-MIN$ and $DECREASE-KEY$ functions.

Heaps are often used in applications, but require some sort of translation schema to map array indices to application objects. This is often accomplished with a handle: auxiliary information stored in the heap elements and / or application object that provide enough information to complete the mapping. For example, the handle in the application object might only contain the heap index, and only be accessed by the priority queue code, and the heap keys might contain pointers to their corresponding application objects. But since heap array indices change throughout their lifespan, the heap implementation must update the application objects whenever it swaps the position of heap elements-- typically this overhead is $O(n)$, worst-case.

An alternative would be to maintain an extra external data structure (like hash table) capable of mapping heap elements to application code objects. This way, application objects need to embellishment. IF the mapping is inefficient, however, this could add significant overhead.

int max_heap_maximum(Heap h) {
  if (h.size < 1)
    return -1; // heap underflow
  return h.array[0];
}

int max_heap_extract_max(Heap h) {
  int max = max_heap_maximum(h);
  heap.array[0] = heap.array[heap.size--];
  max_heapify(h, 0);
  return max;
}

void max_heap_increase_key(Heap h, int x, int k) {
  if (h.array[k] < x) {
    h.error = PQ_KEY_TOO_SMALL;
  } else {
    h.array[x] = k;

    for (
      int i = x;
      i < 0 && h.array[parent(i)] < h.array[i];
      i = parent(i)
    ) {
      int tmp = h.array[i];
      h.array[i] = h.array[parent(i)];
      h.array[parent(i)] = tmp;
    }
  }
}

void max_heap_insert(Heap h, int x, int k) {
  if (h.size == HEAP_MAX) {
    h.error = HEAP_OVERFLOW;
  } else {
    h.size++;
  h.array[h.size] = k;
  max_heap_increase_key(h, x, k);

  }
}

TODO: this code is bad. I need to reflect more deeply about how priority queues work, and then probably just make them their own struct. Also actually deciding the best error-handling strategy for Heap would probably go a long way.