The address of this page is:
    http://csc.csudh.edu/suchenek/MakeHeap.html
                            



/**

 * Copyright: Marek A. Suchenek and other parties
 * @author Suchenek at csudh dot edu
 *
 
*           Heapsort
 *
 * The use for the purpose of classroom
 * instruction or scientific research
 * is allowed with proper attribution
 * to the copyright holder or holders.
 *
 * This Java program runs under NetBeans 6.9
 *
 * An analysis of this program has been published in:
 *
 * Suchenek, M.A. :
 *
"Elementary Yet Precise Worst-Case Analysis of Floyd's Heap-Construction Program,"
 *
Fundamenta Informaticae 120 (2012), pp 75--92,
 * doi: 10.3233/FI-2012-751. Print ISSN: 0169-2968. Electronic ISSN: 1875-8681.
 *
Errata in PDF.
 *
 * Plain text file of this program is available here.
 */

package heap;

public class MakeHeap {
    private int N; //the number of elements in the heap
    private int[] heap; //the heap; itemArray[0] is not a part of the heap

    private void FixHeap(int q)
    {
        int x = heap[q]; //x is the root of the almost subheap that may have to be demoted
        int lp = 2*q; //lp is the index of the first child of x
        while (lp <= N) //q, the index of x, is not the index of a leaf
        {
        if (lp < N) //the second child of x exists
        {
            if (heap[lp+1] > heap[lp]) //the second child of x is larger than the first child
                lp++; //lp is the index of the larger child of x
        }
            if (x >= heap[lp]) //x is not lesser than any of its children
            {
                heap[q] = x; //so, x belongs at index q and the heap is fixed
                return;
            }
            heap[q] = heap[lp]; //promote the larger child of x
            q = lp; //demote x
            lp *= 2; //lp is the index of the first child of x
        }
        heap[q]=x; //x has been demoted to an index of leaf and so the heap is fixed
    }

    public MakeHeap(int[] elements)
    {
        N = elements.length - 1; // elements[0] is not used for sorting
        heap = elements; // intentional side effect
        for (int i = N/2; i > 0; i--) FixHeap(i);
    }

    public int RemoveMax()
    {
     if (N==0) return -9999;
     //here count != 0
        int maxItem = heap[1]; //remove the root and
        heap[1] = heap[N]; //fill the vacancy with the last element
        N--;
        FixHeap(1);
        return maxItem;
        }

    public void RemoveAll()
    {
        for (int i = N; i > 0; i--) heap[i] = RemoveMax();
    }

    public static void Heapsort(int[] array)
    {
        MakeHeap H = new MakeHeap(array);
        H.RemoveAll();
    }

    public static void main(String[] args)
    {
        int[] Array;
        for (int N = 0; N<=21; N++)
        {
            Array = new int[N + 1]; //Array[0] is not used for sorting
            for (int i = 1; i <= N; i++)
                Array[i] = (int)(Math.sqrt(97)*(13*i + 1)*(19*i + 2)+i - 17)%1000;
//            for (int i = 1; i <= N; i++)
//                Array[i] = -i;
            System.out.println("N = " + N);
            System.out.println("Array to be sorted:");
            for (int i = 1; i <= N; i++)
                System.out.print(Array[i] + " ");
            System.out.println();

            Heapsort(Array);

            System.out.println("Sorted array:");
            for (int i = 1; i <= N; i++)
                System.out.print(Array[i] + " ");
                System.out.println();
        }
    }
}
/*
run:
N = 0
Array to be sorted:

Sorted array:

N = 1
Array to be sorted:
879
Sorted array:
879
N = 2
Array to be sorted:
879 621
Sorted array:
621 879
N = 3
Array to be sorted:
879 621 229
Sorted array:
229 621 879
N = 4
Array to be sorted:
879 621 229 702
Sorted array:
229 621 702 879
N = 5
Array to be sorted:
879 621 229 702 40
Sorted array:
40 229 621 702 879
N = 6
Array to be sorted:
879 621 229 702 40 243
Sorted array:
40 229 243 621 702 879
N = 7
Array to be sorted:
879 621 229 702 40 243 312
Sorted array:
40 229 243 312 621 702 879
N = 8
Array to be sorted:
879 621 229 702 40 243 312 247
Sorted array:
40 229 243 247 312 621 702 879
N = 9
Array to be sorted:
879 621 229 702 40 243 312 247 46
Sorted array:
40 46 229 243 247 312 621 702 879
N = 10
Array to be sorted:
879 621 229 702 40 243 312 247 46 711
Sorted array:
40 46 229 243 247 312 621 702 711 879
N = 11
Array to be sorted:
879 621 229 702 40 243 312 247 46 711 241
Sorted array:
40 46 229 241 243 247 312 621 702 711 879
N = 12
Array to be sorted:
879 621 229 702 40 243 312 247 46 711 241 637
Sorted array:
40 46 229 241 243 247 312 621 637 702 711 879
N = 13
Array to be sorted:
879 621 229 702 40 243 312 247 46 711 241 637 898
Sorted array:
40 46 229 241 243 247 312 621 637 702 711 879 898
N = 14
Array to be sorted:
879 621 229 702 40 243 312 247 46 711 241 637 898 24
Sorted array:
24 40 46 229 241 243 247 312 621 637 702 711 879 898
N = 15
Array to be sorted:
879 621 229 702 40 243 312 247 46 711 241 637 898 24 15
Sorted array:
15 24 40 46 229 241 243 247 312 621 637 702 711 879 898
N = 16
Array to be sorted:
879 621 229 702 40 243 312 247 46 711 241 637 898 24 15 872
Sorted array:
15 24 40 46 229 241 243 247 312 621 637 702 711 872 879 898
N = 17
Array to be sorted:
879 621 229 702 40 243 312 247 46 711 241 637 898 24 15 872 595
Sorted array:
15 24 40 46 229 241 243 247 312 595 621 637 702 711 872 879 898
N = 18
Array to be sorted:
879 621 229 702 40 243 312 247 46 711 241 637 898 24 15 872 595 182
Sorted array:
15 24 40 46 182 229 241 243 247 312 595 621 637 702 711 872 879 898
N = 19
Array to be sorted:
879 621 229 702 40 243 312 247 46 711 241 637 898 24 15 872 595 182 635
Sorted array:
15 24 40 46 182 229 241 243 247 312 595 621 635 637 702 711 872 879 898
N = 20
Array to be sorted:
879 621 229 702 40 243 312 247 46 711 241 637 898 24 15 872 595 182 635 953
Sorted array:
15 24 40 46 182 229 241 243 247 312 595 621 635 637 702 711 872 879 898 953
N = 21
Array to be sorted:
879 621 229 702 40 243 312 247 46 711 241 637 898 24 15 872 595 182 635 953 137
Sorted array:
15 24 40 46 137 182 229 241 243 247 312 595 621 635 637 702 711 872 879 898 953
BUILD SUCCESSFUL (total time: 0 seconds)
*/




This website has been up in its present form since year 2000. All rights reserved.


...loading