PRIORITY QUEUE aka HEAP

"obsolete data structure"  Anything a heap can do, a red-black (or an AVL) can do better and more.

The one real advantage a heap has is that you don't need pointers, you can run the whole thing out of an array.

Queue is first in first out (some people call queues FIFOs).  A priority queue first in, highest priority out.

For example:  You have a shared printer.  For most slobs, you submit your jobs and they're printed in the order received.  (this is called a "print queue.")  BUT, whenever your boss wants to print, his job prints before all those others who have been waiting.

This is a priority queue.

We use a heap to represent a priority queue.  A heap is a binary tree such that every node is greater than either of its children.