Create Binary Heap sorting by using Java

A binary heap is a set of nodes with keys arranged in a complete heap-ordered binary tree


A binary tree is heap-ordered if the key in each node is larger than (or equal to) the keys in that nodes two children (if any).


Rule: 
In a heap, the parent of the node in position k is in position k/2; and, conversely, the two children of the node in position k are in positions 2k and 2k + 1. We can travel up and down by doing simple arithmetic on array indices: to move up the tree from a[k] we set k to k/2; to move down the tree we set k to 2*k or 2*k+1.


Top-down heapify (sink). If the heap order is violated because a node's key becomes smaller than one or both of that node's children's keys, then we can make progress toward fixing the violation by exchanging the node with the larger of its two children. This switch may cause a violation at the child; we fix that violation in the same way, and so forth, moving down the heap until we reach a node with both children smaller, or the bottom.






public class Heap {

    public static void main(String[] args) {
        String[] a = new String[]{
        "C","Z","S", "O","R","T", "E", "X", "A", "M", "P", "L", "E", "A","F"
        };
        Heap.sort(a);

       
        Integer[] b = new Integer[]{10,8,7,1,2,4,3,6,5};
        Heap.sort(b);
     
    }
   
public static void sort(Comparable[] pq) {
       int N = pq.length;
     
       //build the heap
       // start from 1 to N/2, as the bottom level(which N located with be sorted by sink method;
       for (int k = N/2; k >= 1; k--){
           sink(pq, k, N);
       }
       
       //sort the array
       while (N > 1) {
        //in place sorting, exchange the top(max or min) with the bottom value, and re-organzie the heap(N-1) again.
           exch(pq, 1, N--);
           sink(pq, 1, N);
       }    
       show(pq);
 
   }

  /***********************************************************************
   * Helper functions to restore the heap invariant.
   **********************************************************************/
   private static void sink(Comparable[] pq, int k, int N) {
       while (2*k <= N) {
           int j = 2*k;
           if (j < N && less(pq, j, j+1)) j++;
           if (!less(pq, k, j)) break;
           exch(pq, k, j);
           k = j;
       }
   }

  /***********************************************************************
   * Helper functions for comparisons and swaps.
   * Indices are "off-by-one" to support 1-based indexing.
   **********************************************************************/
   private static boolean less(Comparable[] pq, int i, int j) {
       return pq[i-1].compareTo(pq[j-1]) < 0;
   }

   private static void exch(Object[] pq, int i, int j) {
       Object swap = pq[i-1];
       pq[i-1] = pq[j-1];
       pq[j-1] = swap;
   }

   // print array to standard output
   private static void show(Comparable[] a) {
       for (int i = 0; i < a.length; i++) {
           System.out.print(a[i] + " ");
        }  
       System.out.println();
    }
}