What sorting algorithm is this, and how does it work? (If there isn't a name or well-known resource for it.)

Question

It's been nearly ten years since I took my DSA class. I've looked through Wikipedia's list of sorting algorithms but none stand out as being this one. It's part of a priority queue implementation, and it appears part of the sorting happens in the push function (EnQueue) while the other in the pop function (DeQueue).

Here's the original Mathematica code, but since most aren't familiar with Mathematica, I've translated a little bit, below each function.

EnQueue[q : queue[ar_, n_, pred_], val_] := Module[{i, j},
  If[n == Length[ar], ar = Join[ar, makeArray@Length@ar]];
  n++; ar[[n]] = val;
  i = n;
  While[True,
   j = Quotient[i, 2];
   If[j < 1 || pred[ar[[j]], ar[[i]]],
    Break[]
    ];
   ar[[{i, j}]] = {ar[[j]], ar[[i]]};
   i = j;
   ];
  q
  ]

The EnQueue function first checks if the number of elements n has reached the size of the heap ar, and if so, doubles the heap. Next, it increments the number of elements and stores the new element at that index (Mathematica indices are 1-based, not 0-based). Then, it sets i to that index (of the new element), and enters a loop that sets j to floor(i/2), i.e. some element in the middle of the heap. Now, if j < 1 (which is equivalent to checking if i == 1, as far as I can tell), or if ar[j] (the element in the middle) should be ahead of ar[i] (the new element), then we break. Otherwise, we swap the elements at i and j, and continue; so in the second iteration, we start with i pointing to the middle, and j pointing to quarter-way.

DeQueue[queue[ar_, n_, pred_]] := 
 Module[{i, j, res = ar[[1]]},
  ar[[1]] = ar[[n]]; ar[[n]] = Null; n--;
  j = 1;
  While[j <= Quotient[n, 2],
   i = 2 j;
   If[i < n && pred[ar[[i + 1]], ar[[i]]],
    i++
    ];
   If[pred[ar[[i]], ar[[j]]],
    ar[[{i, j}]] = {ar[[j]], ar[[i]]};
    ];
   j = i];
  res]

Meanwhile, DeQueue returns the front of the heap, and moves the back of the heap to the front (and unsets the back, and decrements the number of elements). Then, starting with j pointing to the front, it enters a loop that starts by setting i to double j. If i is within bounds (pointing to an element) but is out of order with respect to the next element, i is incremented. If i is in order with respect to j (the front; in other words, if the front is out of order with respect to i), then the two positions are swapped, and j is set to the position i was at. We continue the loop until j passes the middle.

It's mostly the bolded part above I don't understand. I think what it's doing is sorting half the heap on DeQueue, and doing some part of the sort for a new element in EnQueue, but I'm not sure...

Answer 1

Enqueue seems like a min-heap routine to me
https://en.wikipedia.org/wiki/Heap_(data_structure)
https://en.wikibooks.org/wiki/Data_Structures/Min_and_Max_Heaps

Dequeue removes the top item of a heap, which is stored in the first item of an array, then replaces it with the last item of the array and sifts it down the heap, swapping it each time with a child as long as a child is smaller than the item (and smaller than its sibling, if it has one). That stops when there's no smaller child, i.e. when the item reaches the heap bottom or it is smaller than its children (or child, it there's only one).

EDIT: Words 'enqueue' & 'dequeue' suggest it's a queue. The algorithm is a binary heap implemented in an array, so this is a priority queue.