From 8bbe1d4a61288a2998fbae05ac61ef50a8cfc4e6 Mon Sep 17 00:00:00 2001
From: Mike Buland <eichlan@xagasoft.com>
Date: Tue, 19 Feb 2008 00:15:18 +0000
Subject: Added heap logic, about to make a heap class.
---
misc/heap.cpp | 119 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 119 insertions(+)
create mode 100644 misc/heap.cpp
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 @@
+#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;
+}
+
--
cgit v1.2.3