Heap sort
Priority queue
Many applications need to deal with ordered elements, but they don’t have to be all ordered or sorted all at once. In many cases, we’ll collect a few elements, process the element with the largest current key, and then collect more elements, and process the element with the largest current key. In this case, an appropriate data structure should support two operations: deleting the maximum element and inserting the element. This data type is called a priority queue.
Priority queues are used similarly to queues (delete the oldest element) and stacks (delete the latest element).
public class TopM {
public static void main(String[] args) { // Prints the largest Af line in the input stream
int M = Integer.parseInt(args[0]); MinPQ<Transaction> pq =new MinPQ<Transaction>(M + l);
while (StdIn.hasNextLine()) { // Create an element for the next line of input and put it in the priority queue
pq.insert(newThe Transaction (StdIn. ReadLine ()));if (pq.sizeQ > M)
pq.de1Min() ; // If there are M+1 elements in the priority queue, delete the smallest element
} // The largest A/ elements are in the priority queue
Stack<Transaction> stack = new Stack <Transaction>();
while(! pq.isEmpty()) stack.push(pq.delMin()) ;for(Transaction t : stack) StdOut.println(t); }}Copy the codeFrom the command line, enter an integer M and a series of strings, each line representing a transaction. This code calls MinPQ and prints M lines with the largest number. It uses the Transaction class to construct a priority queue with numbers as keys. When the size of the priority queue exceeds M, the smallest element is deleted. After all transactions are entered, the program prints the largest M transactions from the priority queue in descending order. This code is equivalent to putting all the transactions on a stack, walking through the stack to reverse their order and print them out in increased order.
Array implementation (unordered)
The code of the insert() method and stack push() method exactly the same. To remove the largest element, we can add an inner loop similar to the selected-sort loop that swaps the largest element with the boundary element and then removes it, just as we did with the pop () method on the stack. Like stacks, we can also add code to resize arrays to ensure that the data structure is at least a quarter full and never overflows.
Array implementation (ordered)
The alternative is to add code to the insert() method that moves all the larger elements one space to the right to keep the array in order and insert sort. Thus, the largest element is always on one side of the array, and the deletion of the largest element in the priority queue is the same as the pop() operation on the stack.
Linked list notation
Again, we can use list-based pushdown code as a base, and then either modify pop() to find and return the largest element, or modify push() to keep all elements in reverse order and pop() to remove and return the first element of the list (the largest element)
The definition of the heap
Data structure binary heap can well implement the basic operation of priority queue.
A binary tree is called heap-ordered when each node is greater than or equal to two of its children.
Binary heap representation
If we use Pointers to represent heap-ordered binary trees, then each element needs three Pointers to find its upper and lower nodes (one for each parent and two children). If we use full binary trees, the representation becomes particularly convenient. Complete binary trees can be represented with arrays and no Pointers. The method is to place the nodes of the binary tree in a hierarchical order, with the root node at position 1, its children at positions 2 and 3, and the children at positions 4, 5, 6 and 7, and so on.
The algorithm of the heap
Bottom-up heap ordering (float up)
Insert elements. We add the new element to the end of the array, increase the heap size and float the new element up to the appropriate position.
private void swim(int k) {
while (k > 1 && less(k / 2,k)) {
exch(k / 2,k);
k = k / 2; }}Copy the codeTop to bottom heap ordering (sinking)
Delete the largest element. We remove the largest element from the top of the array and put the last element of the array at the top, reducing the heap size and sinking the element into place.
private void sink(int k) {
while (2 * k <= N) {
int j = 2 * k;
if (j < N && less(j,j + 1))
j++;
if(! less(k,j))break; exch(k,j); k = j; }}Copy the codeHeap-based priority queues
public class MaxPQ<Key extends Comparable<Key» {
private Key[] pq; // Heap-based fully pressed binary tree
private int N = 0; // Stored in p q [l.. N], p q [0] not used
public MaxPQ(int maxN) {
pq = (Key[]) new Comparable[maxN+1];
}
public boolean isEmpty(a) {
return N == 0;
}
public int size(a) {
return N;
}
public void insert(Key v) {
pq[++N] = v;
swim(N);
}
public Key delMax(a) {
Key max = pq[1]; // Get the maximum element from the root
exch(1, N--); // Swap it with the last node
pq[N+1] = null; // Prevent trespassing
sink(1); // Restore heap order
return max;
}
See the code box at the beginning of this section for the implementation of the helper methods
private boolean less (int i, int j)
private void exch(int i, int j)
private void swim (int k)
private void sink (int k)
}
Copy the codeFor a heap-based priority queue with # elements, insert elements need no more than (lgN + 1) comparisons, and remove the largest element requires no more than 2lgN comparisons.
Heapsort algorithm
public static void sort(Comparable[] a) {
int N = a.length;
for (int k = N / 2; k >= 1; k--) {
sink (a,k,N);
}
while (N > 1) {
exch(a,1,N--);
sink(a,1,N); }}Copy the codeThis code sorts the elements from a[1] to a[N] using the sink() method (sink() has been modified to take a and N as arguments). The for loop constructs the heap, then the while loop swaps the largest elements A [1] and A [N] and fixes the heap, repeating until the heap is empty.
To sort N elements, heap sort requires less than (2N LGN + 2N) comparisons (and half the swaps).
Performance characteristics of various sorting algorithms
Quicksort is the fastest general sorting algorithm. In most practical cases, quicksort is the best choice.
Java.util.arrays.sort () actually represents a series of sorts, depending on the type of argument:
- Each primitive data type has a different sorting method;
- A sorting method that applies to all data types that implement the Comparable interface;
- A sorting method for data types that implement the Comparator’s Comparator.
Find the KTH smallest element in a set of numbers
public static Comparable select(COmparable[] a,int k) {
StdRandom.shuffle(a);
int lo = 0,hi = a.length - 1;
while (hi > lo) {
int j = partition(a,lo,hi);
if (j == k) {
return a[k];
} else if (j > k) {
hi = j - 1;
} else if (j < k) {
lo = j + 1; }}return a[k];
}
Copy the code