1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
|
#include <stdio.h>
#include <stdlib.h>
void printHeap( int *aiHeap, int iHeapFill )
{
printf("graph G {\n");
for( int j = 0; j < iHeapFill; j++ )
{
if( j*2+1 < iHeapFill )
printf(" %d -- %d;\n",
j, j*2+1
);
if( j*2+2 < iHeapFill )
printf(" %d -- %d;\n",
j, j*2+2
);
}
for( int j = 0; j < iHeapFill; j++ )
{
printf(" %d [label=\"%d\"];\n",
j, aiHeap[j]
);
}
printf("}\n");
}
void heapPush( int iNum, int *aiHeap, int &iHeapFill )
{
for( int j = 0; j < iHeapFill; )
{
if( iNum < aiHeap[j] )
{
int iTmp = aiHeap[j];
aiHeap[j] = iNum;
iNum = iTmp;
}
if( iNum <= aiHeap[j*2+1] )
{
j = j*2+1;
continue;
}
else
{
j = j*2+2;
continue;
}
}
aiHeap[iHeapFill] = iNum;
for( int j = iHeapFill; j >= 0; )
{
int k = (j-1)/2;
if( aiHeap[k] <= aiHeap[j] )
break;
int iTmp = aiHeap[k];
aiHeap[k] = aiHeap[j];
aiHeap[j] = iTmp;
j = k;
}
iHeapFill++;
}
int heapPop( int *aiHeap, int &iHeapFill )
{
int iRet = aiHeap[0];
int j;
for( j = 0; j < iHeapFill; )
{
if( aiHeap[j*2+1] >= aiHeap[j*2+2] && j*2+2 < iHeapFill )
{
aiHeap[j] = aiHeap[j*2+2];
j = j*2+2;
}
else if( j*2+1 < iHeapFill )
{
aiHeap[j] = aiHeap[j*2+1];
j = j*2+1;
}
else
break;
}
aiHeap[j] = aiHeap[iHeapFill-1];
iHeapFill--;
return iRet;
}
int main( int argc, char *argv[] )
{
int *aiHeap = new int[40];
int iHeapFill = 0;
int iNums = atoi( argv[1] );
int iOffs = atoi( argv[2] );
char cDo = argv[3][0];
for( int j = 0; j < iNums; j++ )
{
int iNum = rand()%20;
if( cDo == 'y' ) printf("%d ", iNum );
heapPush( iNum, aiHeap, iHeapFill );
}
if( cDo == 'y' ) printf("\n");
for( int j = 0; j < iOffs; j++ )
{
if( cDo == 'y' )
printf("%d ", heapPop( aiHeap, iHeapFill ) );
else
heapPop( aiHeap, iHeapFill );
}
if( cDo == 'y' ) printf("\n");
else printHeap( aiHeap, iHeapFill );
delete[] aiHeap;
return 0;
}
|
