#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define MAX_HEAP 100
typedef enum { false, true } bool;
typedef struct {
char small;
char middle;
char large;
} Hex_num;
typedef struct {
Hex_num data; // This is a priority as well as data
} HNode;
typedef struct {
HNode items[MAX_HEAP + 1];
int num;
} Heap;
void InitHeap(Heap *pheap);
bool IsEmpty(Heap *pheap);
bool IsFull(Heap *pheap);
void Insert(Heap *pheap, Hex_num data);
Hex_num Delete(Heap *pheap);
void HeapSort(Hex_num a[], int n);
Hex_num *CreateHexNum(char str[]);
void GetInput();
int main() {
Hex_num a[5] = { { '0','F','0' },{ '1','2','3' },{ 'F','F','F' },{ 'C','C','C' },{ '0','D','3' } }; // 0F0321FFFCCC3D0
HeapSort(a, 5);
// GetInput();
/*
5
0F0321FFFCCC3D0
*/
return 0;
}
void HeapSort(Hex_num a[], int n) {
Heap heap;
InitHeap(&heap);
// Insert all elements to the heap.
for (int i = 0; i < n; i++)
Insert(&heap, a[i]);
// Remove all elements from the heap.
for (int i = n - 1; i >= 0; i--)
a[i] = Delete(&heap);
for (int i = 0; i < n; i++)
printf("%c%c%c", a
[i
].
large, a
[i
].
middle, a
[i
].
small); }
Hex_num *CreateHexNum(char str[]) {
Hex_num
*res
= (Hex_num
*)malloc(sizeof(Hex_num
)*(n
)); for (int i = 0; i < n; i++) {
res[i].large = str[i * 3];
res[i].middle = str[i * 3 + 1];
res[i].small = str[i * 3 + 2];
}
return res;
}
/* Modify from here */
void InitHeap(Heap *pheap) {
//set number of nodes to 0
pheap->num = 0;
};
bool IsEmpty(Heap *pheap) {
//check if the number of nodes is 0
return pheap->num == 0;
};
bool IsFull(Heap *pheap) {
//check if the number of nodes reached the maximum possible number of heap
return pheap->num == MAX_HEAP;
};
void Insert(Heap *pheap, Hex_num data) {
//set index to last position
int index = pheap->num + 1;
//while we reach the root
while (index>1) {
//get the parent of index
int parent = index / 2;
//compare the new node with its parent
if (compareHex(data, pheap->items[parent].data)<0) { //if new node is smaller
//swap the two nodes
pheap->items[index] = pheap->items[parent];
index = parent;
}
else break; //break from loop if new node is larger than its parent
}
//insert the new node to the final index we found from the loop above
HNode newNode;
newNode.data = data;
pheap->items[index] = newNode;
//increment the number of nodes in the heap
pheap->num++;
};
Hex_num Delete(Heap *pheap) {
//store minimum (item to be deleted)
Hex_num min = pheap->items[1].data;
//get the last node in the heap
HNode last = pheap->items[pheap->num];
int index = 1, child;
//compare the parent (starting from root) with all of its children
while (child = GetHighPrioityChild(pheap, index)) {
//if the child's data is smaller than the last node
if (compareHex(pheap->items[child].data, last.data)<0) {
//swap the parent and child
pheap->items[index] = pheap->items[child];
index = child;
}
else break; //break from the loop if child's data is larger than last node
}
//set last node to the index we found from the loop above
pheap->items[index] = last;
//decrement the number of nodes in the heap
pheap->num--;
//return the value that is deleted from the heap
return min;
};
int compareHex(Hex_num num1, Hex_num num2) {
int firstNum[3], secondNum[3]; //array to store hex_num
//convert hex characters to integer and save it to integer array
firstNum[0] = convertToInt(num1.large);
firstNum[1] = convertToInt(num1.middle);
firstNum[2] = convertToInt(num1.small);
secondNum[0] = convertToInt(num2.large);
secondNum[1] = convertToInt(num2.middle);
secondNum[2] = convertToInt(num2.small);
//convert hex numbers to decimal
int temp = firstNum[0] * 16 * 16 + firstNum[1] * 16 + firstNum[2];
int temp2 = secondNum[0] * 16 * 16 + secondNum[1] * 16 + secondNum[2];
//return the difference between the first hex num and the second hex num
return temp - temp2;
}
int GetHighPrioityChild(Heap *pheap, int idx) {
if (idx * 2 > pheap->num) return 0; //case where there is no child node
else if (idx * 2 == pheap->num) return idx * 2; //case where there is only a left child.
else {
//get the index of left and right child
int left = idx * 2, right = idx * 2 + 1;
//compare left and right child and return the node with smaller data
if (compareHex(pheap->items[left].data, pheap->items[right].data) < 0) {
return left;
}
else {
return right;
}
}
}
//function to convert hex character to integer value
int convertToInt(char c) {
switch (c) {
case '0': return 0; break;
case '1': return 1; break;
case '2': return 2; break;
case '3': return 3; break;
case '4': return 4; break;
case '5': return 5; break;
case '6': return 6; break;
case '7': return 7; break;
case '8': return 8; break;
case '9': return 9; break;
case 'A': return 10; break;
case 'B': return 11; break;
case 'C': return 12; break;
case 'D': return 13; break;
case 'E': return 14; break;
case 'F': return 15; break;
default: return 0; break;
}
}
/* Modify to here */