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

(limited to '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