1 /*

2 * Title: heap.cpp
3 * Abstract: This program allows users to perform operations on heaps.
4 * Author: William Baker
5 * ID: 1235
6 * Date: 06/18/2019
7 */
8
9 #include <iostream>
10 #include <new>
11 #include <fstream>
12 #include <cstring>
13 #include <sstream>
14 #include <string>
15 #include <stdio.h>
16 #include <string.h>
17
18 using namespace std;
19
20 int main () {
21 string value, str, row, index;
22 int length, newValue;
23 int flag = -1;
24 int count;
25 int success = -1;
26 cout << "Input Size: ";
27 cin >> value;
28 count = stoi(value) + 1;
29
30 cout << "Enter numbers: ";
31 cin.ignore();
32 getline(cin, str);
33 stringstream ss(str);
34 string token;
35 int * heap;
36 heap = new int[count];
37
38 int i = 1;
39 while(getline(ss, value, ' ')){
40
41 heap[i] = stoi(value);
42 i++;
43 }
44
45 int notAHeap = 0;
46 for (int i = (count -1)/2 ; i > 0; i--){
47 int k = i;
48 int v = heap[k];
49 int isHeap = 0;
50 while (isHeap == 0 && 2*k<=count){
51 int j = 2*k;
52 if(j < count){
53 if(heap[j] < heap[j+1]){
54 j = j+ 1;
55 }
56 }
57
58 if(v >= heap[j]){
59 isHeap=1;
60 }
61 else{
62 heap[k] = heap[j];
63 k = j;
64 notAHeap = 1;
65 }
66 }
67 heap[k] = v;
68 }
69 if(notAHeap == 0){
70 cout << "This is a heap.";
71 }
72
73 else{
74 cout << "\nThis is not a heap. \nHeap Constructed: " << heap[1];
75 for (int i = 2; i < count; i++){
76 cout << ", " << heap[i];
77 }
78 }
79 int choice;
80 while(choice != 3){
81 cout<< "\nSelect an Operation\n\t1. Insert a number.\n\t2. Delete the
max.\n\t3. Heapsort and Quit.\n";
82 cin >> value;
83 choice = stoi(value);
84 if (choice == 1){
85 //*******************************************************
86 //Adding a new VALUE
87 //*******************************************************
88 cout <<"Enter a number: ";
89 cin >> value;
90 newValue = stoi(value);
91 count = count + 1;
92 int * tempHeap;
93 tempHeap = new int[count];
94
95 for (int i = 0; i < count -1; i++){
96 tempHeap[i] = heap[i];
97 }
98 tempHeap[count-1] = newValue;
99
100 int x = count - 1;
101 while (x > 1){
102 if(tempHeap[x] > tempHeap[x/2]){
103 int temp = tempHeap[x/2];
104 tempHeap[x/2] = tempHeap[x];
105 tempHeap[x] = temp;
106
107 x = x/2;
108 }
109 else{
110 x = 0;
111 }
112 }
113 heap = tempHeap;
114 cout << "\nUpdated Heap: " << heap[1];
115 for (int i = 2; i < count; i++){
116 cout << ", " << heap[i];
117 }
118 cout << "\n";
119 }
120
121 else if(choice == 2){
122 //*******************************************************
123 //removing MAX Value
124 //*******************************************************
125 if(count>1){
126 heap[1] = heap[count - 1];
127 count = count-1;
128 int * tempHeap;
129 tempHeap = new int[count];
130
131 for (int i = 0; i < count; i++){
132 tempHeap[i] = heap[i];
133 }
134
135 int x = 1;
136
137 while (2 * x <= count){
138 int maxIndex = 0;
139 if (tempHeap[x] < tempHeap[2 * x]){
140 maxIndex = 2*x;
141 if(2*x+1<count){
142 if (tempHeap[x] < tempHeap[2*x+1] && tempHeap[2*x+1] >
tempHeap[2*x] ){
143 maxIndex = 2*x+1;
144 }
145 }
146 }
147
148 else{
149 if(2*x+1<count){
150 if (tempHeap[x] < tempHeap[2*x+1]){
151 maxIndex = 2*x+1;
152 }
153 }
154 }
155
156 if (maxIndex > 0){
157 int temp = tempHeap[maxIndex];
158 tempHeap[maxIndex] = tempHeap[x];
159 tempHeap[x] = temp;
160 }
161 else{
162 x = count;
163 }
164 }
165 heap = tempHeap;
166
167 cout << "\nUpdate Heap: ";
168 if (count>1){
169 cout << heap[1];
170 for (int i = 2; i < count; i++){
171 cout << ", " << heap[i];
172 }
173 }
174 cout << "\n";
175 }
176 }
177
178
179
180
181 else if(choice == 3){
182 int sortedCount = count-1;
183 int * sorted;
184 sorted = new int[sortedCount];
185
186 int x = 1;
187 for(int i = 0; i <= sortedCount; i++){
188 sorted[i] = heap[1];
189 heap[1] = heap[count - 1];
190 count = count-1;
191 int * tempHeap;
192 tempHeap = new int[count];
193 for (int j = 0; j < count; j++){
194 tempHeap[j] = heap[j];
195 }
196
197 int x = 1;
198
199 while (2 * x <= count){
200 int maxIndex = 0;
201 if (tempHeap[x] < tempHeap[2 * x]){
202 maxIndex = 2*x;
203 if(2*x+1<count){
204 if (tempHeap[x] < tempHeap[2*x+1] && tempHeap[2*x+1] >
tempHeap[2*x] ){
205 maxIndex = 2*x+1;
206 }
207 }
208 }
209
210 else{
211 if(2*x+1<count){
212 if (tempHeap[x] < tempHeap[2*x+1]){
213 maxIndex = 2*x+1;
214 }
215 }
216 }
217
218 if (maxIndex > 0){
219 int temp = tempHeap[maxIndex];
220 tempHeap[maxIndex] = tempHeap[x];
221 tempHeap[x] = temp;
222 }
223 else{
224 x = count;
225 }
226 }
227 heap = tempHeap;
228
229 }
230
231 //heap = tempHeap;
232 cout << "\nHeap Sort: " << sorted[0];
233 for (int i = 1; i < sortedCount; i++){
234 cout << ", " << sorted[i];
235 }
236 cout << "\nBye!\n";
237 }
238 }
239 }
240