Data and analysis of algorithm

Question

1. illustrate the operation of HEAPSORT on the array A = {15, 113, 12, 125, 17, 117, 120, 18, 14}. Show, visually, the binary tree just after the BUILD-HEAP is called and at the end of each of the HEAPIFY operation.

2. Write a complete algorithm that determines if a given number is a favorite number or not. Use the following definition of a favorite number. The algorithm should take one parameter, the number, and print a message that says if the number is favorite or not. A number N (greater than 0) is said to be favorite if the sum of all its factors equals the number. For example, 6 is a favorite number because 1 + 2 + 3 = 6, and 1, 2 and 3 are favorite of 6. 28 is also a favorite number because 1 + 2 + 4 + 7 + 14 = 28, and the individual numbers are all factors of 28

Answer 1

//Source code uploaded to RESOURCES section under this link

using namespace std;

#include <iostream>

#include <string.h>

#include <stdlib.h>

#include <stdio.h>

#define MAX_HEAP_SIZE (100)

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

{

int * intPtr1 = (int*)rec1;

int * intPtr2 = (int*)rec2;

int iNum1 = *intPtr1;

int iNum2 = *intPtr2;

//cout << "comparing " << iNum1 << " and " << iNum2 << endl;

return(iNum1-iNum2);

}

typedef struct _THeapSort

{

int heap[MAX_HEAP_SIZE];

int count;

} * THeapSort;

void Heap_Init(THeapSort heapsort)

{

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

heapsort->count=0;

}

int Heap(THeapSort heapsort, int newData)

{

int iReturn=-1;

if (heapsort->count<MAX_HEAP_SIZE)

{

//cout << " heap inserted :" << newData << endl;

heapsort->heap[(heapsort->count)++]=newData;

qsort(heapsort->heap,heapsort->count,sizeof(int),CompareInt);

}

else

{

iReturn = heapsort->heap[0];

//cout << "heap output " << iReturn << endl;

heapsort->heap[0]=newData;

qsort(heapsort->heap,heapsort->count,sizeof(int),CompareInt);

}

return(iReturn);

}

Go()

{

struct _THeapSort heapSort;

Heap_Init(&heapSort);

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

while (!feof(fptr))

{

int intNum;

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

// cout << "incoming..." << intNum << endl;

int iReturn = Heap(&heapSort,intNum);

if (iReturn>0)

{

cout << iReturn << endl;

}

}

fclose(fptr);

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

{

cout << heapSort.heap[iLoop] << endl;

}

}

bool IsFavoriteNumber(int n)

{

int sum=1;

for (int iLoop=2; iLoop<n; iLoop++)

{

if ((n % iLoop)==0)

{

sum += iLoop;

}

}

return( sum==n);

}

int main()

{

Go();

if (IsFavoriteNumber(6)) { cout << "6 is a favorite number " << endl; }

if (IsFavoriteNumber(28)) { cout << "28 is a favorite number " << endl; }

if (IsFavoriteNumber(55)) { cout << "55 is a favorite number " << endl; }

}