Advanced Sorting - Advanced Topics in Java: Core Concepts in Data Structures - page 265

We can think of priority as an integer—the bigger the integer, the higher the priority.
Immediately, we can surmise that if we implement the queue as a max-heap, the item with the highest priority
will be at the root, so it can be easily removed. Reorganizing the heap will simply involve “sifting down” the last item
from the root.
Adding an item will involve placing the item in the position after the current last one and sifting it up until it finds
its correct position.
To delete an arbitrary item from the queue, we will need to know its position. Deleting it will involve replacing it
with the current last item and sifting it up or down to find its correct position. The heap will shrink by one item.
If we change the priority of an item, we may need to sift it either up or down to find its correct position. Of course,
it may also remain in its original position, depending on the change.
In many situations (for example, a job queue on a multitasking computer), the priority of a job may increase over
time so that it eventually gets served. In these situations, a job moves closer to the top of the heap with each change;
thus, only sifting up is required.
In a typical situation, information about the items in a priority queue is held in another structure that can be
quickly searched, for example a binary search tree. One field in the node will contain the index of the item in the array
used to implement the priority queue.
Using the job queue example, suppose we want to add an item to the queue. We can search the tree by job
number, say, and add the item to the tree. Its priority number is used to determine its position in the queue. This
position is stored in the tree node.
If, later, the priority changes, the item's position in the queue is adjusted, and this new position is stored in the
tree node. Note that adjusting this item may also involve changing the position of other items (as they move up or
down the heap), and the tree will have to be updated for these items as well.

9.5 Sorting a List of Items with Quicksort
At the heart of quicksort is the notion of partitioning the list with respect to one of the values called a pivot . For
example, suppose we are given the following list to be sorted:

num

53 12 98 63 18 32 80 46 72 21

1 2 3 4 5 6 7 8 9 10

We can partition it with respect to the first value, 53. This means placing 53 in such a position that all values to
the left of it are smaller and all values to the right are greater than or equal to it. Shortly, we will describe an algorithm
that will partition num as follows:

num

21 12 18 32 46 53 80 98 72 63

1 2 3 4 5 6 7 8 9 10

The value 53 is used as the pivot . It is placed in position 6. All values to the left of 53 are smaller than 53, and
all values to the right are greater. The location in which the pivot is placed is called the division point ( dp , say). By
definition, 53 is in its final sorted position.
If we can sort num[1..dp-1] and num[dp+1..n] , we would have sorted the entire list. But we can use the same
process to sort these pieces, indicating that a recursive procedure is appropriate.