HeapSorter.java
Created with JBuilder
/**
* Sorts an array from lo to hi by building successive heap structures.
An array A[lo:hi] is said to satisfy the "heap property" if
for i = 0,.., hi - lo:
A[lo + i] <= A[lo + 2 * i + 1]  and
A[lo + i] < = A[lo + 2 * i + 2],
whenever these indices are in the range [lo..hi].
* Heapsort is part of the hard-split/easy-join family since all the work is done * in the split phase. *

Copyright 2000 - Dung X. Nguyen - All rights reserved.

*/ public class HeapSorter extends ASorter { /** * Heapifies A from lo to hi. * @param A an array of int. * @param lo the low index of A. * @param hi the high index of A. */ public HeapSorter(int[] A, int lo, int hi) { for (int cur = (hi + lo + 1) / 2; cur >= lo; cur--) { Heapifier.Singleton.siftDown (A, lo, cur, hi); } } /** * Swaps A[lo] with A[hi] and sift A[lo] down to hi - 1. * Assumes A satisfy the heap property. * @return hi */ public int split(int[] A, int lo, int hi) { int temp = A[hi]; A[hi] = A[lo]; A[lo] = temp; Heapifier.Singleton.siftDown (A, lo, lo, hi - 1); return hi; } /** * Does nothing, assuming s == hi. */ public void join(int[] A, int lo, int s, int hi) { } public static void main(String[] args) { //int[] A = {}; //int[] A = {50}; //int[] A = {50, 80}; //int[] A = {80, 50}; //int[] A = {50, 80, 20}; //int[] A = {80, 50, 20}; int[] A = {999, 50, 80, 20, 60, 90, 40, 30, 70, 10, -999}; int arrayLen = A.length; System.out.println ("A ="); for (int i = 0; i < arrayLen; i++) { System.out.print (A[i] + " "); } int lo = 1; int hi = arrayLen - 2; System.out.println ("\nHeapifying A[" + lo + "..." + hi + "]"); ASorter sorter = new HeapSorter (A, lo, hi); // Only a part of A is to be heapified. System.out.println ("\nHeapified A ="); for (int i = 0; i < A.length; i++) { System.out.print (A[i] + " "); } System.out.println ("\nSorting A[" + lo + "..." + hi + "]"); sorter.sort (A, lo, hi); // Only a part of A is to be sorted. System.out.println ("Sorted A ="); for (int i = 0; i < A.length; i++) { System.out.print (A[i] + " "); } System.out.println ("\nDone"); } }
HeapSorter.java
Created with JBuilder