aboutsummaryrefslogtreecommitdiff
path: root/misc/heap.cpp
diff options
context:
space:
mode:
authorMike Buland <eichlan@xagasoft.com>2012-11-05 22:41:51 +0000
committerMike Buland <eichlan@xagasoft.com>2012-11-05 22:41:51 +0000
commitec05778d5718a7912e506764d443a78d6a6179e3 (patch)
tree78a9a01532180030c095acefc45763f07c14edb8 /misc/heap.cpp
parentb20414ac1fe80a71a90601f4cd1767fa7014a9ba (diff)
downloadlibbu++-ec05778d5718a7912e506764d443a78d6a6179e3.tar.gz
libbu++-ec05778d5718a7912e506764d443a78d6a6179e3.tar.bz2
libbu++-ec05778d5718a7912e506764d443a78d6a6179e3.tar.xz
libbu++-ec05778d5718a7912e506764d443a78d6a6179e3.zip
Converted tabs to spaces with tabconv.
Diffstat (limited to '')
-rw-r--r--misc/heap.cpp188
1 files changed, 94 insertions, 94 deletions
diff --git a/misc/heap.cpp b/misc/heap.cpp
index a913ef8..d558b0c 100644
--- a/misc/heap.cpp
+++ b/misc/heap.cpp
@@ -3,117 +3,117 @@
3 3
4void printHeap( int *aiHeap, int iHeapFill ) 4void printHeap( int *aiHeap, int iHeapFill )
5{ 5{
6 printf("graph G {\n"); 6 printf("graph G {\n");
7 for( int j = 0; j < iHeapFill; j++ ) 7 for( int j = 0; j < iHeapFill; j++ )
8 { 8 {
9 if( j*2+1 < iHeapFill ) 9 if( j*2+1 < iHeapFill )
10 printf(" %d -- %d;\n", 10 printf(" %d -- %d;\n",
11 j, j*2+1 11 j, j*2+1
12 ); 12 );
13 if( j*2+2 < iHeapFill ) 13 if( j*2+2 < iHeapFill )
14 printf(" %d -- %d;\n", 14 printf(" %d -- %d;\n",
15 j, j*2+2 15 j, j*2+2
16 ); 16 );
17 } 17 }
18 for( int j = 0; j < iHeapFill; j++ ) 18 for( int j = 0; j < iHeapFill; j++ )
19 { 19 {
20 printf(" %d [label=\"%d\"];\n", 20 printf(" %d [label=\"%d\"];\n",
21 j, aiHeap[j] 21 j, aiHeap[j]
22 ); 22 );
23 } 23 }
24 printf("}\n"); 24 printf("}\n");
25} 25}
26 26
27void heapPush( int iNum, int *aiHeap, int &iHeapFill ) 27void heapPush( int iNum, int *aiHeap, int &iHeapFill )
28{ 28{
29 for( int j = 0; j < iHeapFill; ) 29 for( int j = 0; j < iHeapFill; )
30 { 30 {
31 if( iNum < aiHeap[j] ) 31 if( iNum < aiHeap[j] )
32 { 32 {
33 int iTmp = aiHeap[j]; 33 int iTmp = aiHeap[j];
34 aiHeap[j] = iNum; 34 aiHeap[j] = iNum;
35 iNum = iTmp; 35 iNum = iTmp;
36 } 36 }
37 37
38 if( iNum <= aiHeap[j*2+1] ) 38 if( iNum <= aiHeap[j*2+1] )
39 { 39 {
40 j = j*2+1; 40 j = j*2+1;
41 continue; 41 continue;
42 } 42 }
43 else 43 else
44 { 44 {
45 j = j*2+2; 45 j = j*2+2;
46 continue; 46 continue;
47 } 47 }
48 } 48 }
49 aiHeap[iHeapFill] = iNum; 49 aiHeap[iHeapFill] = iNum;
50 for( int j = iHeapFill; j >= 0; ) 50 for( int j = iHeapFill; j >= 0; )
51 { 51 {
52 int k = (j-1)/2; 52 int k = (j-1)/2;
53 if( aiHeap[k] <= aiHeap[j] ) 53 if( aiHeap[k] <= aiHeap[j] )
54 break; 54 break;
55 55
56 int iTmp = aiHeap[k]; 56 int iTmp = aiHeap[k];
57 aiHeap[k] = aiHeap[j]; 57 aiHeap[k] = aiHeap[j];
58 aiHeap[j] = iTmp; 58 aiHeap[j] = iTmp;
59 j = k; 59 j = k;
60 } 60 }
61 iHeapFill++; 61 iHeapFill++;
62} 62}
63 63
64int heapPop( int *aiHeap, int &iHeapFill ) 64int heapPop( int *aiHeap, int &iHeapFill )
65{ 65{
66 int iRet = aiHeap[0]; 66 int iRet = aiHeap[0];
67 67
68 int j; 68 int j;
69 for( j = 0; j < iHeapFill; ) 69 for( j = 0; j < iHeapFill; )
70 { 70 {
71 if( aiHeap[j*2+1] >= aiHeap[j*2+2] && j*2+2 < iHeapFill ) 71 if( aiHeap[j*2+1] >= aiHeap[j*2+2] && j*2+2 < iHeapFill )
72 { 72 {
73 aiHeap[j] = aiHeap[j*2+2]; 73 aiHeap[j] = aiHeap[j*2+2];
74 j = j*2+2; 74 j = j*2+2;
75 } 75 }
76 else if( j*2+1 < iHeapFill ) 76 else if( j*2+1 < iHeapFill )
77 { 77 {
78 aiHeap[j] = aiHeap[j*2+1]; 78 aiHeap[j] = aiHeap[j*2+1];
79 j = j*2+1; 79 j = j*2+1;
80 } 80 }
81 else 81 else
82 break; 82 break;
83 } 83 }
84 aiHeap[j] = aiHeap[iHeapFill-1]; 84 aiHeap[j] = aiHeap[iHeapFill-1];
85 iHeapFill--; 85 iHeapFill--;
86 return iRet; 86 return iRet;
87} 87}
88 88
89int main( int argc, char *argv[] ) 89int main( int argc, char *argv[] )
90{ 90{
91 int *aiHeap = new int[40]; 91 int *aiHeap = new int[40];
92 int iHeapFill = 0; 92 int iHeapFill = 0;
93 93
94 int iNums = atoi( argv[1] ); 94 int iNums = atoi( argv[1] );
95 int iOffs = atoi( argv[2] ); 95 int iOffs = atoi( argv[2] );
96 char cDo = argv[3][0]; 96 char cDo = argv[3][0];
97 97
98 for( int j = 0; j < iNums; j++ ) 98 for( int j = 0; j < iNums; j++ )
99 { 99 {
100 int iNum = rand()%20; 100 int iNum = rand()%20;
101 if( cDo == 'y' ) printf("%d ", iNum ); 101 if( cDo == 'y' ) printf("%d ", iNum );
102 heapPush( iNum, aiHeap, iHeapFill ); 102 heapPush( iNum, aiHeap, iHeapFill );
103 } 103 }
104 if( cDo == 'y' ) printf("\n"); 104 if( cDo == 'y' ) printf("\n");
105 105
106 for( int j = 0; j < iOffs; j++ ) 106 for( int j = 0; j < iOffs; j++ )
107 { 107 {
108 if( cDo == 'y' ) 108 if( cDo == 'y' )
109 printf("%d ", heapPop( aiHeap, iHeapFill ) ); 109 printf("%d ", heapPop( aiHeap, iHeapFill ) );
110 else 110 else
111 heapPop( aiHeap, iHeapFill ); 111 heapPop( aiHeap, iHeapFill );
112 } 112 }
113 if( cDo == 'y' ) printf("\n"); 113 if( cDo == 'y' ) printf("\n");
114 else printHeap( aiHeap, iHeapFill ); 114 else printHeap( aiHeap, iHeapFill );
115 115
116 delete[] aiHeap; 116 delete[] aiHeap;
117 return 0; 117 return 0;
118} 118}
119 119
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-15 04:21:42 +0000