PPPeck313/323-DA-Algorithms-2-Heap-Sort

323 2-Heap-Sort

CSC 323-32: Project 2 (C++/Java)

Preston Peck

Due date: Sept. 20, 2016

**** Algorithm steps for heap sort:

Step 1: open the input file;
1.1: read and count the number of date item in the input file
1.2: close the file
1.3: dynamically allocate the PQAry of the size count+1
1.4: initallize PQAry[0] to 0

Step 2: call buildPQAry

Step 3: call deletePQAry

**** Algorithm steps for buildHeap:

Step 1: open the input file for the second time

Step 2: data <-- get a data item from the input file

Step 3: insertOneDataItem (data)
3.1: bubbleUp

Step 4: printPQAry (print the content of PQAry up to the first 10 items of the PQAry to out1file

Step 5: repeat step 2 - 4 while input file is NOT empty

Step 6: close the input file

**** Algorithm steps for deleteRoot:

Step 1: open the output file

Step 2: deleteRoot
2.1: print the root to outfile2
2.2: bubbleDown

Step 3: printPQAry (print the content of PQAry up to the first 10 items of the PQAryto outfile1

Step 4: repeat step 2 and 3 while PQAry is NOT empty

Step 5: close the two output files

INPUT

23
82 12 53
9 39 2 13
30
61
21
45
18 19 42
53 4 93 34 8 36 37
10 11
7 8
5 10 20

OUTPUT

23
23 82
12 82 23
12 53 23 82
9 12 23 82 53
9 12 23 82 53 39
2 12 9 82 53 39 23
2 12 9 13 53 39 23 82
2 12 9 13 53 39 23 82 30
2 12 9 13 53 39 23 82 30 61
2 12 9 13 21 39 23 82 30 61
2 12 9 13 21 39 23 82 30 61
2 12 9 13 21 18 23 82 30 61
2 12 9 13 21 18 19 82 30 61
2 12 9 13 21 18 19 82 30 61
2 12 9 13 21 18 19 53 30 61
2 4 9 12 21 18 19 13 30 61
2 4 9 12 21 18 19 13 30 61
2 4 9 12 21 18 19 13 30 61
2 4 9 12 8 18 19 13 30 21
2 4 9 12 8 18 19 13 30 21
2 4 9 12 8 18 19 13 30 21
2 4 9 12 8 18 19 13 30 21
2 4 9 12 8 11 19 13 30 21
2 4 7 12 8 9 19 13 30 21
2 4 7 12 8 8 19 13 30 21
2 4 5 12 8 7 19 13 30 21
2 4 5 12 8 7 10 13 30 21
2 4 5 12 8 7 10 13 30 21

4 8 5 12 10 7 10 13 30 21
5 8 7 12 10 8 10 13 30 21
7 8 8 12 10 9 10 13 30 21
8 10 8 12 20 9 10 13 30 21
8 10 9 12 20 11 10 13 30 21
9 10 10 12 20 11 19 13 30 21
10 12 10 13 20 11 19 39 30 21
10 12 11 13 20 18 19 39 30 21
11 12 18 13 20 23 19 39 30 21
12 13 18 30 20 23 19 39 34 21
13 20 18 30 21 23 19 39 34 61
18 20 19 30 21 23 42 39 34 61
19 20 23 30 21 36 42 39 34 61
20 21 23 30 37 36 42 39 34 61
21 30 23 34 37 36 42 39 93 61
23 30 36 34 37 45 42 39 93 61
30 34 36 39 37 45 42 53 93 61
34 37 36 39 53 45 42 53 93 61
36 37 42 39 53 45 82 53 93 61
37 39 42 53 53 45 82 61 93
39 53 42 53 93 45 82 61
42 53 45 53 93 61 82
45 53 82 53 93 61
53 53 82 61 93
53 93 82 61
61 93 82
82 93
93

2 4 5 7 8 8 9 10 10 11 12 13 18 19 20 21 23 30 34 36 37 39 42 45 53 53 61 82 93