HEAP-SORT: Implement a HEAP data structure where continuous deletion on the HEAP outputs the given data in descending orde in C

Question

HEAP-SORT: Implement a HEAP data structure where continuous deletion on the HEAP outputs the given data in descending order in c

Answer 1

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define MAX_HEAP_SIZE (100)

//#define _BINARY_HEAP

#define POP_FIRST (0)

#define POP_LAST (1)

typedef struct _THeapSort

{

int heap[MAX_HEAP_SIZE];

int count;

} *THeapSort;

int compareCallback( const void * rec1, const void * rec2)

{

int * intPtr1 = (int *)rec1;

int * intPtr2 = (int *)rec2;

int iNum1 = (*intPtr1);

int iNum2 = (*intPtr2);

return(iNum1-iNum2);

}

void Heap_Init(THeapSort heapSort)

{

memset(heapSort->heap,0,sizeof(int)*MAX_HEAP_SIZE);

heapSort->count=0;

}

int Heap_Push(THeapSort heapSort, int num)

{

int iReturn=0;

if (heapSort->count<MAX_HEAP_SIZE)

{

// printf("Pushing %d AND count = %d \n",num,heapSort->count);

#ifdef _BINARY_HEAP

heapSort->heap[(heapSort->count)++] = num;

qsort(heapSort->heap,heapSort->count,sizeof(int),compareCallback);

#else

if (heapSort->count==0)

{

heapSort->heap[(heapSort->count)++] = num;

}

else

{

int j=heapSort->count-1;

while (heapSort->heap[j]>num) //can be made more generic using the compare callback

{

heapSort->heap[j+1] = heapSort->heap[j];

j--;

if (j<0) { break; }

}

heapSort->heap[++j] = num;

heapSort->count++;

}

#endif

}

else //the heap is full

{

iReturn=-1;

}

return(iReturn);

}

int Heap_Pop(THeapSort heapSort, int popFlag)

{

int iReturn=-1;

if (popFlag==POP_LAST)

{

int iIndexPos = heapSort->count - 1;

iReturn = heapSort->heap[iIndexPos];

heapSort->heap[iIndexPos] = 0;

heapSort->count--;

}

else

{

iReturn = heapSort->heap[0];

int iLoop;

for ( iLoop=1; iLoop<heapSort->count; iLoop++)

{

heapSort->heap[iLoop-1] = heapSort->heap[iLoop];

}

heapSort->heap[heapSort->count-1]=0;

heapSort->count--;

}

//printf("Popping %d \n",iReturn);

return(iReturn);

}

int HeapSort (THeapSort heapSort, int sortOrder)

{

int iLoop=0;

FILE * fptr = fopen("E:\\input.dat","r");

while (feof(fptr)==0)

{

int iNum=0;

fscanf(fptr,"%d",&iNum);

int iReturn = Heap_Push(heapSort,iNum);

if (iReturn!=0)

{

int iNumOutput = Heap_Pop(heapSort,sortOrder);

printf("%d ",iNumOutput);

Heap_Push(heapSort,iNum);

}

}

for (iLoop=0; iLoop<MAX_HEAP_SIZE; iLoop++)

{

int iNumOutput = Heap_Pop(heapSort,sortOrder);

printf("%d ",iNumOutput);

}

fclose(fptr);

}

int main()

{

int iReturn=0;

struct _THeapSort heapSort;

Heap_Init(&heapSort);

HeapSort(&heapSort,POP_FIRST);

return(iReturn);

}