기본 콘텐츠로 건너뛰기

Heap

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <stdbool.h>
#define MAXSIZE 10

typedef struct {
int heapAry[MAXSIZE];
int last;
int size;
int maxSize;
}HEAP;

HEAP* heapCreate (int maxSize){
HEAP *heap = (HEAP*)malloc (sizeof (HEAP));
if(!heap) return NULL;

heap->last = -1; //the index (works as top in stack)
heap->size = 0;

//wtf?
heap->maxSize = (int) pow(2, ceil(log2(maxSize))) - 1;
//force heap size to power of 2-1

int array[maxSize];
//allocate the array[maxSize] times size of void*
return heap;

}

void reheapUp(HEAP* heap, int childLoc){
int parent = 0; // start a traverse from the parent
int hold = 0;
//if child is root node, right goes to return
if(childLoc){
//if the child is not null == not root node
parent = (childLoc - 1) / 2;
if(heap->heapAry[childLoc] > heap->heapAry[parent]){
//if compare returns 1 or true,
//it means child is bigger than parent
//child is greater than parent == swap
hold = heap->heapAry[parent];
heap->heapAry[parent] = heap->heapAry[childLoc];
heap->heapAry[childLoc] = hold;
reheapUp(heap, parent);
//now the child which was bigger than parent is in parent
//we compare new parent to compare its parent to find the order
//in the heap by calling this function again
}
//if c-p is in right order, return
}
return;
}
//
//void reheapDown(HEAP* heap, int root){
// int hold = NULL;
// int leftData = NULL;
// int rightData = NULL;
// int largeLoc = 0;
// int last = 0;
//
// last = heap->last;
//
// if((root*2 + 1) <= last){//left subtree there is at least one child
// leftData = heap->heapAry[root * 2 + 1];
//
//
// if((root * 2 + 2) <= last){
// rightData  = heap->heapAry[root * 2 + 2];
// }
//
// else {
// rightData = NULL;
// }
//
// if(!rightData ||
// leftData > rightData){
// //qhwn leftdata is bigger than right data
// largeLoc = root * 2 + 1;
// }
//
// else{
// //if there is right data or right data is bigger than left one
// largeLoc = root * 2 + 2;
// }
//
// if(heap->heapAry[root] < heap->heapAry[largeLoc]){
// //if largeLoc is bigger than parent, need to swap down
// hold = heap->heapAry[root];
// heap->heapAry[root] = heap->heapAry[largeLoc];
// heap->heapAry[largeLoc] = hold;
// reheapDown(heap, largeLoc);
//
// }
// }
// return;
//}
bool heapInsert(HEAP* heap, int dataPtr){
if(heap->size >= heap->maxSize){
//the most recent one's index is out of boundary
return false;
}
++(heap->last);
++(heap->size);
heap->heapAry[heap->last] = dataPtr;
// printf("just added %d and saved is \n", dataPtr,
// heap->heapAry[heap->last]);
reheapUp(heap, heap->last);
return true;
}
//
//bool heapDelete(HEAP* heap, int* dataOutPtr){
// if(heap->size == 0) return false;
//
// *dataOutPtr = heap->heapAry[0];
// heap->heapAry[0] = heap->heapAry[heap->last];
// (heap->last)--;
// (heap->size)--;
// reheapDown(heap,0);
// return true;
// //nothing to delete, return
//}

void Print(HEAP* heap){
for(int i = 0; i < MAXSIZE - 1; i++){

printf("%d", heap->heapAry[i]);
if(heap->heapAry[i] != 35) printf(", ");
else printf("\n");
}
}

int main(){
int arr[10] = {10,12, 89,236, 758, 45,21,96,35};
HEAP* myheap = heapCreate(MAXSIZE);

for(int i = 0; i < MAXSIZE; i++){
heapInsert(myheap, arr[i]);
}

printf("Contents of the Max-heap:\n");
Print(myheap);

return 0;
}

/*Not everything works and failed to use void ** since I didnt know how to implement it  using type casting but i passed the assignment so whatever!!*/
라벨:

댓글

댓글 쓰기

이 블로그의 인기 게시물

JS 5.5 task6 Create an extendable calculator

<HTML>   <body>   </body>   <script> function Calculator() {   let methods = {     "-" : (a, b) => a - b,     "+" : (a, b) => a + b   };   //methods is an object which keeps key for operators   //and value to return the actual operation values   //each returns the result of operation that key(operator) does   this.calculate = function (str){     //calculate is one element in the function Calculator     //it takes the string and returns the value     //in the function element list is delimeted by , not ;     let split = str.split(" "),     a = +split[0],     op = split[1],     b = split [2]     if(!methods[op] || isNaN(a) || isNaN(b)) {       return NaN; // error handling     }     return methods[op](a,b);   }   this.addMethod = function(name, func){     methods[name] = func;     //this is how to add new key and ele to object   } } let powerCalc = new Calculator; powerCalc.addMethod("*&
댓글 쓰기
자세한 내용 보기

JS 5.7 task5 Store read dates

<HTML>   <body>   </body>    <script>    let messages = [        {text: "Hello", from: "John"},        {text: "How goes?", from: "John"},        {text: "See you soon", from: "Alice"}    ];    let readMap = new WeakMap();    alert(readMap.size);    readMap.set(messages[0], new Date(2019, 3, 5));   </script> </HTML> <!-- task4 needed weakSet to save simply readmessage, this task needs to save THE TIME IT WAS READ along with the message itself the message out of the set or map means it hasn't been read I kinda feel good and bad at the same time to happen to read the solution but I do get to think more about the difference with tasks and be more available to understand the main contents so I think, its good? -->
댓글 쓰기
자세한 내용 보기

How to set base url when deployed in Heroku? : base url and axios

https://stackoverflow.com/questions/47164330/axios-api-calls-in-heroku/47165888 baseUrl = process.env.baseURL || "http://localhost:5000" Even more stable way https://stackoverflow.com/questions/52129849/how-to-get-the-base-url-variable-on-a-deployed-heroku-node-app const production  = 'https://examplePage.com'; const development = 'http://localhost:3000/'; const url = (process.env.NODE_ENV ? production : development); process.env.NODE_ENV will resolve to undefined if you are running on localhost production mode. and return production if you have deployed the app production mode.
댓글 쓰기
자세한 내용 보기