Example of Huffman Algorithm by using Heap

Example of Huffman algorithm by using heap.

NOTIFICATION: These examples are provided for educational purposes. Using this code is under your own responsibility and risk. The code is given ‘as is’. I do not take responsibilities of how they are used.

huffman.c:

```/*
* Program: Huffman using heap
* Author: Alejandro G. Carlstein
*/

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAX_CODE 1000000
#define MAX_LETTERS 4
#define MAX_HEAP 10
#define LEFT(i) ((i << 1) + 1)
#define RIGHT(i) ((i << 1) + 2)
#define PARENT(i) (((i + 1) >> 1) - 1)
#define DIV_BY_2(i) (i >> 1)
#define DBG_LV0 1
#define DBG_LV1 1
#define DBG_LV2 1
#define DBG_LV3 0
#define LETTER_A 65
#define DIR_LEFT '0'
#define DIR_RIGHT '1'

#define ROOT_INDEX 0

struct Data{
int letter;
int frequency;
int left;
int right;
int parent;
}Data;

struct Data data[MAX_LETTERS];
int code[MAX_CODE][MAX_LETTERS];
int heap[MAX_HEAP];

void printCodes(int *codes, int numCodes);
void printStructArray(struct Data array[], int length);
int huffman(void);
void buildMinHeap(int array[], int heapSize);
void minHeapify(int array[], int index, int heapSize);
int heapMin(int array[]);
int heapExtractMin(int array[], int *length);
void insertMinHeap(int array[], int value, int *length);
void exchange(int *a, int *b);
void printArray(int array[], int length);
int isLeft(struct Data array[], int indexLeft, int indexRight);
void test1();
void test2();

int num_letters;
int numCodes = 0;

int main(int argc, char* argv[]){

if (DBG_LV3) printStructArray(data, num_letters);

int i;
for (i = 0; i < num_letters; ++i)
heap[i] = i;

printf('ROOT(huffman): %d \n', huffman());

if (DBG_LV1) printStructArray(data, num_letters);

//decodeMessage(data, num_letters, &code[0][0], numCodes);

if (DBG_LV2) printf('\n');

return 0;

}

for (num_letters = 0; num_letters < MAX_LETTERS; ++num_letters){
scanf('%d', &data[num_letters].frequency);
data[num_letters].letter = LETTER_A + num_letters;
data[num_letters].left = -1;
data[num_letters].right = -1;
data[num_letters].parent = -1;

heap[num_letters] = -1;
}

}

int c;
int indexCode = 0;

numCodes = 0;

while ((c = getchar()) != EOF){

if (c != ' ' && c != '\n'){
if (DBG_LV3) printf('[%d][%d]%c{%d}\n', numCodes, indexCode, c, c);
code[numCodes][indexCode] = (int)c;
++indexCode;
}

if (c == '\n'){
code[numCodes][indexCode] = -1;
if (DBG_LV3) printf('{{%d}}\n', code[numCodes][indexCode]);
++numCodes;
indexCode = 0;

}
}

if (DBG_LV3){
printf('CODES: \n');
printCodes(&code[0][0], numCodes);

}

}

void printCodes(int *codes, int numCodes){
if (DBG_LV2) printf('printCodes(numCodes: %d)\n', numCodes);

int indexCode, index;
int indexArray;

for (indexCode = 0; indexCode < numCodes; ++indexCode){

indexArray = indexCode * sizeof(int);

for (index = 0; codes[indexArray + index] > -1 ; ++index){

printf('[%d][%d]: %c(%d) \n',
indexArray, index,
codes[indexArray + index], codes[indexArray + index]);

}

printf('\n');

}

}

void printStructArray(struct Data array[], int length){
if (DBG_LV0) printf('printStructArray()\n');

int i;
for (i = 0; i < length; ++i)
printf('[%d]%c - %d (L:%d, R:%d, P:%d) \n',
i, data[i].letter, data[i].frequency, data[i].left, data[i].right, data[i].parent);
}

int huffman(void){
if (DBG_LV0) printf('\nHUFFMAN()\n');

int length = num_letters;
int i;
int left;
int right;
int parent;
int n = length;

length++;

printf('length: %d\n\n', length);

if (DBG_LV1) printArray(heap, num_letters);

for (i = 0; i < n - 1; ++i){

left = heapExtractMin(heap, &length);

printf('length: %d\n\n', length);

right = heapExtractMin(heap, &length);

parent = left + right;

data[left].parent = parent;
data[right].parent = parent;

printf('length: %d\n\n', length);

if (DBG_LV2){
printf('left: %d, ', left);
printf('right: %d, ', right);
printf('parent: %d\n', parent);
printArray(heap, length);
}

insertMinHeap(heap, parent, &length);

printf('length: %d\n\n', length);
//--*length;

}

if (DBG_LV1) printArray(heap, num_letters);

return heapExtractMin(heap, &length);
}

void buildMinHeap(int array[], int heapSize){

int index;

for (index = DIV_BY_2(heapSize); index >= ROOT_INDEX; --index){

minHeapify(array, index, heapSize);

}

}

void minHeapify(int array[], int index, int heapSize){

int left, right, smallest;

smallest = index;
left = LEFT(index);
right = RIGHT(index);

// Find smallest value
if (left < heapSize && array[left] < array[index])
smallest = left;

if (right < heapSize && array[right] < array[smallest])
smallest = right;

if (smallest != index){

// Exchange
exchange(&array[index], &array[smallest]);

// Rebuild heap region
minHeapify(array, smallest, heapSize);

}

}

int heapMin(int array[]){
return array[ROOT_INDEX];
}

int heapExtractMin(int array[], int *length){
if (DBG_LV0) printf('heapExtractMin()\n');

if (length < 0){
printf('[X] Error: heap overflow!\n');
return -1;
}

--*length;

int heapSize = *length;

int min = array[ROOT_INDEX];

--heapSize;

printf('exchange: array[%d]: %d, array[%d]:%d \n',
ROOT_INDEX, array[ROOT_INDEX],
heapSize, array[heapSize]);

exchange(&array[ROOT_INDEX], &array[heapSize]);

--heapSize;

minHeapify(array, ROOT_INDEX, heapSize);

return min;
}

void insertMinHeap(int array[], int value, int *length){

if (DBG_LV0) printf('insertMinHeap(value: %d, length: %d)\n',
value, *length);

int heapSize = *length;

++*length;

array[heapSize] = INT_MAX;

if (value > array[heapSize]){
printf('[X] Error: new value is bigger than biggest element!\n');
}else{

array[heapSize] = value;

if (DBG_LV2) printArray(array, *length);

while (heapSize > ROOT_INDEX &&
array[PARENT(heapSize)] > array[heapSize]){

exchange(&array[heapSize], &array[PARENT(heapSize)]);

heapSize = PARENT(heapSize);

}

}

}

void exchange(int *a, int *b){
if (DBG_LV3) printf('exchange()\n');

int temp;
temp = *a;
*a = *b;
*b = temp;
}

void printArray(int array[], int length){
if (DBG_LV0) printf('printArray()\n');

int i;

for (i = 0; i < length; ++i)
printf('[%d]', i);

printf('\n');

for (i = 0; i < length; ++i)
printf(' %d ', array[i]);

if (DBG_LV1) printf('\n\n');
}

int isLeft(struct Data array[], int indexLeft, int indexRight){
if (DBG_LV0) printf('isLeft()\n');

if (array[indexLeft].frequency == array[indexRight].frequency){

if (array[indexLeft].letter < array[indexRight].letter){
return DIR_LEFT;
}else{
return DIR_RIGHT;
}

}else if (array[indexLeft].frequency < array[indexRight].frequency){
return DIR_LEFT;
}else{
return DIR_RIGHT;
}

}

void test1(){
if (DBG_LV1) printf('test1()\n');

int i, length = 5;

if(DBG_LV1)	printf('BUILD HEAP ARRAY:\n');
for(i = 0; i < length; ++i){
heap[i] = i * 2;
printf('heap[%d]: %d \n', i, heap[i]);
}
heap[4] = 1;

buildMinHeap(heap, length);

printArray(heap, length);

insertMinHeap(heap, 3, &length);

printArray(heap, length);
}

void test2(){

int heapLen = num_letters;

printf('heapLen: %d\n', heapLen);

printArray(heap, heapLen);

int result1, result2;

printf('TEST HEAPEXTRACTMIN:\n');
result1 = heapExtractMin(heap, &heapLen);
printf('result1: %d\n', result1);
printArray(heap, heapLen);

printf('heapLen: %d\n', heapLen);

result2 = heapExtractMin(heap, &heapLen);
printf('result2: %d\n', result2);
printArray(heap, heapLen);

printf('heapLen: %d\n', heapLen);

}```

input.txt:

```1
2
3
4
1 0 0
1 0 1
1 1
0```

If you encounter any problems or errors, please let me know by providing an example of the code, input, output, and an explanation. Thanks.

NOTIFICATION: These examples are provided for educational purposes. Using this code is under your own responsibility and risk. The code is given ‘as is’. I do not take responsibilities of how they are used.

```/**
* @author: Alejandro G. Carlstein R. M.
*/
#include <stdio.h>

/* Macros Functions */
#define max(a,b) \
({ typeof (a) _a = (a); \
typeof (b) _b = (b); \
_a > _b ? _a : _b; })

/* Debugging flags */
#define DBG_LV1 0
#define DBG_LV2 1
#define DBG_LV3 0

/* Constants */
#define MAX_NUM_CAR 100
#define MAX_FERRY_LEN 100

enum{ UNKNOWN = -1, LEFT = 0, RIGHT = 1,
};

/* Our dynamic programming table element.  We have the value
* that we can store, and also a way to remember what we selected.
*/
typedef struct{
int length;
int prev_row;
int prev_col;
} Table;

int cars[MAX_NUM_CAR];
int side[MAX_NUM_CAR];
int i, j;
int ferry_len;
int total_cars;

// [ROW] [COLUMN]
Table ferry[MAX_FERRY_LEN][MAX_FERRY_LEN];

/*
*
*/
int main(int argc, char *argv[]){

/* Read the length of the ferry */
scanf('%d', &ferry_len);

// Read length of each car and set side to UNKNOWN since
// we haven't decided yet where they will go
cars[0] = 0;
side[0] = UNKNOWN;
for (i = 1; scanf('%d', &cars[i]) == 1; ++i){
side[i] = UNKNOWN;
};
total_cars = i;

// Initialize the first row and the first column
for (i = 0; i <= ferry_len; ++i)
ferry[0][i].length = ferry[i][0].length = 0;
ferry[0][i].prev_row = ferry[i][0].prev_col = 0;

// Print info
if (DBG_LV2){
printf('\nLength of Ferry: %d \n', ferry_len);
printf('Number of Cars: %d \n\n', total_cars);

for (i = 0; i < total_cars; ++i)
printf('Car[%d]: %d length\n',
i, cars[i]);
printf('************************************\n');
}//end if

// Fill table
int result = recursive_ferry(0,0,0, ferry_len);

if (DBG_LV2){
printf('Result: %d length value\n',  result);
}

if (DBG_LV2)
print_tables();

// Track back foot steps
if (DBG_LV2)  printf('tracking(%d, %d, %d)\n\n', ferry_len, ferry_len, total_cars);
tracking(ferry_len, ferry_len, total_cars);

// Print results
if (DBG_LV2) printf('\n SIDE: \n');

for (i = 1; i < total_cars; ++i)
switch(side[i]){
case UNKNOWN:
if (DBG_LV2) printf('UNKNOWN side[%d]: %d\n', i, side[i]);
break;

case RIGHT:
if (DBG_LV2) printf('RIGHT side[%d]: %d\n', i, side[i]);
printf('right\n');
break;

case LEFT:
if (DBG_LV2) printf('LEFT side[%d]: %d\n', i, side[i]);
printf('left\n');
break;

};

return 0;
}

/*
*
*/
int tracking(int left, int right, int idx_car){

if (1) printf('\ntracking(%d,%d,%d)\n', left, right, idx_car);

if (idx_car < 0)
return;

if (DBG_LV2) printf('.1 ');

if (ferry[left][right].length == 0)
return;

if (DBG_LV2) printf('.2 ');

--idx_car;

int prev_len = (left + right) - cars[idx_car];
int prev_left = left - cars[idx_car];
int prev_right = right - cars[idx_car];

if (DBG_LV2) printf('prev_len: %d = (%d + %d) - %d (car[%d])\n', prev_len, left, right, cars[idx_car], idx_car);

if (ferry[prev_left][right].length == prev_len && prev_left >= 0){

if (DBG_LV2) printf('ferry[prev_LEFT: %d][right: %d] MATCH [from RIGHT]\n', prev_left, right);

side[idx_car] = RIGHT;

tracking (prev_left, right, idx_car);

}else  if (ferry[left][prev_right].length == prev_len && prev_right >= 0){

if (DBG_LV2) printf('ferry[left: %d][prev_RIGHT: %d] MATCH [from LEFT]\n', left, prev_right);

side[idx_car] = LEFT;

tracking (left, prev_right, idx_car);

}else{

if (DBG_LV2) printf('ferry[prev_left][right] and ferry[left][prev_right] DO NOT MATCH\n');
tracking (left, right, idx_car);

}//end if

return;
}

/*
*
*/
int recursive_ferry(int left, int right, int idx_car, int ferry_len){

if (DBG_LV1) printf('r_f(left: %d, right: %d, idx_car: %d (car_len: %d) \n',
left, right, idx_car, cars[idx_car]);

if (left > ferry_len || right > ferry_len || idx_car > total_cars)
return 0;

if (ferry[left][right].length > 0){
if (DBG_LV3) printf('++Return length: %d \n', ferry[left][right].length);
return ferry[left][right].length;
}// end if

// Store value in ferry
ferry[left][right].length += (left + right);

// Record foot steps
int nxt_row = ferry[left][right].prev_row = left;
int nxt_col = ferry[left][right].prev_col = right;

//
int rtn_left = recursive_ferry(left + cars[idx_car], right, idx_car + 1, ferry_len);
int rtn_right = recursive_ferry(left, right + cars[idx_car], idx_car + 1, ferry_len);

if (DBG_LV1 && (rtn_left == 0))
printf('L>');

if (DBG_LV1)
printf('[%d,%d](%d | %d)', nxt_row, nxt_col, rtn_left, rtn_right);

if (DBG_LV1 && (rtn_right == 0))
printf('<R');

if (DBG_LV2) printf('\n');
// Obtain the result of the best route
return max(rtn_left, rtn_right);
}

/*
*
*/
int print_tables(void){

printf('\n\nTABLE\n ');
for (i = 0; i <= ferry_len; ++i)
printf(' %d ',i);
printf('\n');

for (i = 0; i <= ferry_len; ++i){
for (j = 0; j <= ferry_len; ++j){
if (j == 0) printf('%d', i);
printf (' %d ', ferry[i][j].length);
}// end for
printf('\n');
}//end for
printf('\n');

printf('\n TABLE XY\n ');
for (i = 0; i <= ferry_len; ++i)
printf(' [ %d ]',i);
printf('\n');

for (i = 0; i <= ferry_len; ++i){
for (j = 0; j <= ferry_len; ++j){
if (j == 0) printf('%d ', i);
printf('[%d,%d] ', ferry[i][j].prev_row, ferry[i][j].prev_col);
}//end for
printf('\n');
}//end for
printf('\n');

return 0;
}```

If you encounter any problems or errors, please let me know by providing an example of the code, input, output, and an explanation. Thanks.

Example of Knapsack Algorithm

Example of Knapsack algorithm.

NOTIFICATION: These examples are provided for educational purposes. Using this code is under your own responsibility and risk. The code is given ‘as is’. I do not take responsibilities of how they are used.

knapsack.c:

```/**
* Knapsack Algorithm
* @author: Alejandro G. Carlstein R. M.
* @description: Simple Knapsack algorithm
*/
#include <stdio.h>

/* Macros Functions */
#define max(a,b) \
({ typeof (a) _a = (a); \
typeof (b) _b = (b); \
_a > _b ? _a : _b; })

/* Debugging flags */
#define DBG_LV1 0
#define DBG_LV2 0

/* Constants */
#define MAX_STRING_LEN 80
#define MAX_ITEMS 100
#define MAX_WEIGHT 1000

/* This is an item we can put into the knapsack. */
typedef struct{
char name[MAX_STRING_LEN];
int weight;
int value;
} item;

/* Our dynamic programming table element.  We have the value
* that we can store, and also a way to remember what we selected.
*/
typedef struct{
int value;
int prev_row;
int prev_column;
} prog;

void print_table(int num_items, int max_weight);
void print_table_prev_xy(int num_items, int max_weight);

/* The actual DP table, and the items.  Note that we have an extra
* row and column in the table for the 'zero elements' and 'no weight'
* situation.
*/
prog table[MAX_ITEMS + 1][MAX_WEIGHT + 1];

item items[MAX_ITEMS];

int main(int argc, char *argv[]){

int num_items; // Number of items
int w; // Weight
int max_weight;
int n; // Item number;
int i, j;
int diff_weight;

/* Read in the maximum weight and number of items. */
scanf('%d %d', &max_weight, &num_items);

if (DBG_LV2){
printf('\nMax Weight: %d, Number of Items: %d \n\n', max_weight, num_items);
printf('READ ITEMS\nw v name\n');
}//end if

/* Read in the items */
for (n = 0; n < num_items; ++n){
scanf('%d %d %s',
&items[n].weight,
&items[n].value,
items[n].name);

if (DBG_LV1)
printf('%d %d %s\n',
items[n].weight,
items[n].value,
items[n].name);
}//end for

if(DBG_LV2)
printf('\n');

/* Initialize the first row of the table. */
for (w = 0; w <= max_weight; ++w){
table[0][w].value = 0;
table[0][w].prev_row = table[0][w].prev_column = -1;
}//end for

// Fill in the table
// Your code goes here.
// Should be a for loop for the items, a for loop for the weight,
// and inside all of that, a few if statements to determine if you
// can take an item -- and if so, do you want to?
//
// I strongly recommend printing out EVERY DECISION your program
// makes while debugging things -- and feed your program very small
// problems until it's running.
//
// Debugging code is an important skill.  If you can work through a
// problem by hand, you should be able to get your code to solve the
// same thing.

/* Initialize the first column of the table */
for (i= 0; i <= num_items; ++i){
table[i][0].value = 0;
}

if (DBG_LV2){
printf('TABLE VALUES\n');
print_table(num_items, max_weight);
}//end if

if (DBG_LV2){
printf('TABLE PREVIOUS COORDINATES\n');
print_table_prev_xy(num_items, max_weight);
}//end if

// Perform knapsack and find maximun value
for (i = 1; i <= num_items; ++i){

for (w = 0; w <= max_weight; ++w){

table[i][w].prev_row = i - 1;
table[i][w].prev_column = w;

// Check if item fit inside the knapsack

if(items[i - 1].weight <= w) {

int diff_weight = w - items[i - 1].weight;

// Check which value is higher
table[i][w].value = max((items[i - 1].value +
table[i - 1][diff_weight].value),
table[i - 1][w].value);

// Keep track of the previous column
if(table[i][w].value > table[i - 1][w].value)

table[i][w].prev_column = diff_weight;

}else{

table[i][w].value = table[i - 1][w].value;

}//end if

}//end for

}//end for

if (DBG_LV2){
printf('************\n\n');
}//end if

if (DBG_LV2){
printf('TABLE VALUES\n');
print_table(num_items, max_weight);
}//end if

if (DBG_LV2){
printf('TABLE PREVIOUS COORDINATES\n');
print_table_prev_xy(num_items, max_weight);
}//end if

// In my code, the maximum value is here.
// I can use the prev_row and prev_column to trace back the solution.
if (DBG_LV1)
printf('Maximum value is %d\n', table[num_items][max_weight].value);

if (DBG_LV2){
printf('************\n\n');
}//end if

// Print results:

w = max_weight;

int count = -1;

int t;

int total_weight = 0;

item *p_items[MAX_ITEMS];

for(i = num_items;
i > 0;
t = w,
w = table[i][w].prev_column,
i = table[i][t].prev_row){

if(table[i][w].value != table[i - 1][w].value){

total_weight += items[i - 1].weight;

p_items[++count] = &items[i - 1];

}//end if

}//end for

printf('%d\n', table[num_items][max_weight].value);

printf('%d\n', total_weight);

for (i = 0; i <= count; ++i){

printf('%d %d %s \n',
p_items[i]->weight,
p_items[i]->value,
p_items[i]->name);

}//end for

}

/*
*
*/
void print_table(int num_items, int max_weight){

int w,i;

for (i = 0; i <= num_items; ++i){
for (w = 0; w <= max_weight; ++w){
printf('%d ', table[i][w].value);
}//end for
printf('\n');
}//end for
printf('\n');

}

/*
*
*/
void print_table_prev_xy(int num_items, int max_weight){

int w,i;

for (i = 0; i <= num_items; ++i){
for (w = 0; w <= max_weight; ++w){
printf('[%d,%d] ', table[i][w].prev_row, table[i][w].prev_column);
}//end for
printf('\n');
}//end for
printf('\n');

}```

input.txt:

```5
4
2 3 item_A
3 4 item_B
4 5 item_C
5 6 item_D
```

If you encounter any problems or errors, please let me know by providing an example of the code, input, output, and an explanation. Thanks.

Example of Quicksort using Hoarse Partition and Random Partition Algorithms

Example of Quicksort using Hoarse partition and random partition algorithms.

NOTIFICATION: These examples are provided for educational purposes. Using this code is under your own responsibility and risk. The code is given ‘as is’. I do not take responsibilities of how they are used.

quicksort.c:

```/* Framework for the sorting programs.
* Program: 04
* Author: Alejandro G. Carlstein
* Description: This program will implement quicksort
* (using the pseudocode from the book), applying
* the Hoare partition function, and randomization.
* This program should run with data where all the values
* are equal, and also when the data is in sorted
* (or reverse sorted) order.
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_SIZE 1000000

#define DBG_LV1 0
#define DBG_LV2 0

void Quicksort(int array[], int p, int r);
int Hoare_partition(int array[], int p, int r);
int Randomized_partition(int array[], int p, int r);
void Exchange(int *a, int *b);
int Get_random(int min, int max);

int data[MAX_SIZE];

int n;

int main(int argc, char* argv[]){

int i;

int n;

int m = 0;

int begin = 1;

int ia_keys[MAX_SIZE];

srand (time (NULL));

/* Read in the data */
n = 0;
while (scanf('%d', &data[n]) == 1)
++n;

/* Print ou t the data */
if (DBG_LV2)
for (i = 0; i < n; ++i)
printf('[%d] %d\n', i, data[i]);

Quicksort(data, 0, n);

/* Print out the data */
for (i = 0; i < n; ++i)
if (DBG_LV2){
printf('[%d] %d\n', i, data[i]);
}else{
printf('%d\n', data[i]);
}//end if

if (DBG_LV2)
printf('+[10]: %d \n', data[10]);

return 0;
}

/*
* Quicksort
*/
void Quicksort(int array[], int p, int r){

if (DBG_LV1)
printf('Quicksort(p: %d, r: %d)\n', p, r);

int q;

if (p < r){

q = Randomized_partition(array, p, r);

Quicksort(array, p, q);

Quicksort(array, q + 1, r);

}// end if

}

/*
* Hoare partition Book
*/
int Hoare_partition(int array[], int p, int r){

if (DBG_LV1)printf('Hoare_partition_book(p: %d, r:%d)\n', p, r);

int b_done = 1;

// pivot value
int x = array[p];

int i = p - 1;

int j = r + 1;

if (DBG_LV2)
printf('i: %d, j: %d\n', i, j);

while (b_done){

do{
--j;
}while (array[j] < x);

do{
++i;
}while (array[i] > x);

if (DBG_LV2)
printf('+i: %d, j: %d\n', i, j);

if (i < j){

Exchange(&array[i], &array[j]);

}else{

b_done = 0;

}//end if

}// end while

return j;
}

/*
* Randomized partition
*/
int Randomized_partition(int array[], int p, int r){

if (DBG_LV1)
printf('Randomized_partition(p: %d, r: %d)\n', p, r);

int i = Get_random(p, r);

Exchange(&array[i], &array[r]);

return Hoare_partition(array, p, r);

}

/*
* Exchange swap the values holded by two variables
*/
void Exchange(int *a, int *b){

if (DBG_LV1)
printf('Exchange(value a: %d, value b: %d)\n', *a, *b);

int temp;

temp = *a;
*a = *b;
*b = temp;
}

/*
* get random number
*/
int Get_random(int min, int max){

if (DBG_LV1)
printf('Get_random(min: %d, max: %d)\n', min, max);

int rtn = 0;

if (max > min){

rtn = (rand() % (max - min)) + min;

}else{

fprintf(stderr, '[X] ERROR: minimum value cannot exceed maximun value\n');

exit(1);

}//end if

return rtn;
}```

If you encounter any problems or errors, please let me know by providing an example of the code, input, output, and an explanation. Thanks.

Example of Heapsort Algorithm

Example of Heapsort algorithm.

NOTIFICATION: These examples are provided for educational purposes. Using this code is under your own responsibility and risk. The code is given ‘as is’. I do not take responsibilities of how they are used.

heapsort.c:

```/* Framework for the sorting programs.
* Program: 02
* Author: Alejandro G. Carlstein
* Description: This program will read a set of integers from standard
* input and sort them by implement a heap sort using the pseudocode
* from the book Introduction to Algorithms' by Thomas H. Cormen.
* Then print them out in sorted order (smallest to largest).
*/

#include <stdio.h>

#define MAX_SIZE 1000000
#define LEFT(i) ((i << 1) + 1)
#define RIGHT(i) ((i << 1) + 2)
#define DIV_BY_2(i) (i >> 1)

void Max_heapify(int array[], int i, int heap_size);
void Build_max_heap(int array[], int heap_size);
void Exchange(int *a, int *b);
void Heapsort(int array[], int length);

int data[MAX_SIZE];
int n;

int main(int argc, char* argv[]){

int i;
int heap_size;

/* Read in the data */
n = 0;
while (scanf('%d', &data[n]) == 1)
++n;

/* Sort the numbers low to high */
Heapsort(data, n);

/* Print out the data */
for (i = 0; i < n; ++i)
printf('%d\n', data[i]);

return 0;
}

/*
* Max_heapify helps to rebuild the heap region
*/
void Max_heapify(int array[], int i, int heap_size){

int l, r, temp, largest;

l = LEFT(i);

r = RIGHT(i);

// Find Largest value
largest = (l < heap_size && array[l] > array[i]) ? l : i;

if (r < heap_size && array[r] > array[largest]) largest = r;

if (largest != i){

// Exchange
Exchange(&array[i], &array[largest]);

// Rebuild heap region
Max_heapify(array, largest, heap_size);

}// end if

}

/*
* Build_max_heap helps to build the initial heap
*/
void Build_max_heap(int array[], int heap_size){

int i = DIV_BY_2(heap_size);

for (; i > -1; i--){

Max_heapify(array, i, heap_size);

}//end for

}

/*
* Exchange swap the values holded by two variables
*/
void Exchange(int *a, int *b){

int temp;

temp = *a;
*a = *b;
*b = temp;
}

/*
* Heapsort sort an array from the smallest element to the largest
*/
void Heapsort(int array[], int length){

int i;
int	heap_size = length ;

Build_max_heap(data, length);

for (i = (length - 1) ; i > 0; --i){

// Exchange the largest item in the heap region
// to the beginning of the sorted region
Exchange(&data[0], &data[i]);

// Reduce the heap region, increase the sorted region
heap_size--;

// Rebuild the heap region
Max_heapify(data, 0, heap_size);

}//end for

}```

If you encounter any problems or errors, please let me know by providing an example of the code, input, output, and an explanation. Thanks.