|
/**
* 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
*
* Analyses of this program have been published in:
*
* Suchenek,
M.A. :
*
"Worst-case Analysis of Heapsort, Exactly",
* The Computer Journal,
67/3 (2024), pp 812--824.
* Oxford University Press.
* doi: 10.1093/comjnl/bxad007.
*
* and
*
* Suchenek,
M.A. :
* "Elementary
Yet
Precise
Worst-Case
Analysis
of
Floyd's
Heap-Construction
Program,"
* Fundamenta
Informaticae 120/1
(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)
*/
|
|
|
|
|
|
|
|
|
|
