// Heap Sortpackage ralph.sorting;class HeapSort extends SortingTechnique { public void sort() { // Phase 1 : convert array to max-heap (heapify) for (int i = 1; i <= n - 1; i++) trickleUp(i); // Phase 2 : Element at the root is the largest one. Swap it // with element at i & heapify array from 0 to i-1. Do this // recursively for i=n-1 through i=1. for (int i = n - 1; i >= 1; i--) { swap(0, i); trickleDown(0, i - 1); } } private void trickleUp(int node) { if (node <= 0) return; int parent = (node - 1) / 2; if (x[parent] < x[node]) { swap(parent, node); trickleUp(parent); } } // Instead of two different methods trickleUp & trickleDown, // we can have a common routine 'heapify'. But that will degrade // the performance in terms of time complexity. private void trickleDown(int top, int bottom) { int leftChild = 2 * top + 1; int rightChild = leftChild + 1; if (leftChild <= bottom) { // leftChild exists ? int largerChild = (leftChild == bottom || x[leftChild] > x[rightChild]) ? leftChild : rightChild; if (x[top] < x[largerChild]) { swap(largerChild, top); trickleDown(largerChild, bottom); } } }}class HeapSortTestDrive { public static void main(String[] args) { SortingTechnique h1 = new HeapSort(); h1.display("Before Sorting :"); h1.sort(); h1.display("After Sorting :"); }}