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