fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. typedef struct {
  6.   int allocated; /* current allcoation of array */
  7.   int filled;    /* number of items present in the binheap */
  8.   int *array;    /* array of values */
  9. } BinaryHeap;
  10.  
  11. /* Init allocates the structure BinaryHeap and
  12.  * also the membre array with the given size 
  13.  * it also fill allocated (size) and intializes 
  14.  * filled to 0 */
  15. BinaryHeap * Init(int size);
  16.  
  17. /* InsertValue insert value into the binary heap
  18.  * the array is reallocated if necessary (allocated changed 
  19.  * with respect to the new size )
  20.  * filled is incremented by 1 */
  21. void InsertValue(BinaryHeap * heap, int value);
  22.  
  23. /* ExtractMAx returns 0 if the binary heap is empty
  24.  * otherwise it return 1 and fills *val with the maximum 
  25.  * value present in the binary heap
  26.  * filled is decremented by 1  and the max value is removed
  27.  * from the binary heap */
  28. int ExtractMax(BinaryHeap * heap, int * val);
  29.  
  30. /* Destroy frees the structure and the array */
  31. void Destroy(BinaryHeap * heap);
  32.  
  33. void Print(BinaryHeap * heap);
  34.  
  35.  
  36. int main(void) 
  37. {
  38.   char lecture[100];
  39.   int val;
  40.   BinaryHeap * heap;
  41.   heap = Init(10);
  42.  
  43.   fscanf(stdin,"%99s",lecture);
  44.   while (strcmp(lecture,"bye")!=0) {
  45.     if (strcmp(lecture,"insert")==0) {
  46.       fscanf(stdin,"%99s",lecture);
  47.       val = strtol(lecture,NULL,10);
  48.       InsertValue(heap,val);
  49.     } else if (strcmp(lecture,"extract")==0) {
  50.       if(ExtractMax(heap,&val))
  51.       {
  52.         printf("%d\r\n",val);
  53.       }
  54. 	  else if (strcmp(lecture,"print")==0) {
  55.         Print(heap);
  56.       }
  57.     }
  58.     fscanf(stdin,"%99s",lecture);
  59.   }
  60.   Destroy(heap);
  61.   return 0;
  62. }
  63.  
  64.  
  65. BinaryHeap * Init(int size)
  66. {
  67.   BinaryHeap * heap;
  68.   heap = malloc(sizeof(BinaryHeap));
  69.   heap -> allocated = size;
  70.   heap -> filled = 0;
  71.   heap -> array = malloc(heap -> allocated*sizeof(int));
  72.   return heap;
  73. }
  74.  
  75. void InsertValue(BinaryHeap * heap, int value)
  76. {
  77.   if(heap -> filled == heap -> allocated)
  78.   {
  79. 	heap -> allocated = heap -> allocated + 1;
  80. 	heap -> array = realloc(heap -> array,heap -> allocated*sizeof(int));
  81.   }
  82.   heap -> array[heap -> filled] =  value;
  83.   int i = heap -> filled;
  84. 	while (i!=0 && heap -> array[(i-1)/2] < value)
  85. 	{
  86. 		heap -> array[i] = heap -> array[(i-1)/2];
  87. 		heap -> array[(i-1)/2] = value;
  88. 	}
  89. 	heap -> filled = heap -> filled + 1;
  90. }
  91.  
  92. int ExtractMax(BinaryHeap * heap, int *res)
  93. {
  94.   if (heap -> filled == 0)
  95.   {
  96. 	return 0;
  97.   }
  98.   else
  99.   {
  100. 	res = (heap -> array[0]);
  101. 	heap -> filled = heap -> filled -1;
  102. 	heap -> array [0] = heap -> array[heap -> filled];
  103. 	int i = 0;
  104. 	int tampon;
  105. 	while(2*i+2<heap -> filled && (heap -> array[i] < heap -> array[2*i+1] || heap -> array[i] < heap -> array[2*i+2]))
  106. 	{
  107. 		if (heap -> array[2*i+1] < heap -> array[2*i+2])
  108. 		{
  109. 			tampon = heap -> array[2*i+2];
  110. 			heap -> array[2*i+2] = heap -> array[i];
  111. 			heap -> array[i] = tampon;
  112. 			i = 2*i+2;
  113. 		}
  114. 		else if (heap -> array[2*i+1] > heap -> array[2*i+2])
  115. 		{
  116. 			tampon = heap -> array[2*i+1];
  117. 			heap -> array[2*i+1] = heap -> array[i];
  118. 			heap -> array[i] = tampon;
  119. 			i = 2*i+1;
  120. 		}
  121. 	}
  122. 	if(2*i+1<heap -> filled && heap -> array[i] < heap -> array[2*i+1])
  123. 	{
  124. 		tampon = heap -> array[2*i+1];
  125. 			heap -> array[2*i+1] = heap -> array[i];
  126. 			heap -> array[i] = tampon;
  127. 			i = 2*i+1;
  128. 	}
  129. 	return 1;
  130.   }
  131. }
  132.  
  133. void Destroy(BinaryHeap * heap)
  134. {
  135.   /*for (int i=(heap -> filled)-1 ; i = 0 ;i--)
  136.   {
  137. 	free(heap -> array[i]);
  138.   }*/
  139.   free(heap);
  140. }
  141.  
  142. void Print(BinaryHeap * heap)
  143. {
  144. 	for(int i =0; i< heap -> filled; i++)
  145. 	{
  146. 		printf("%d\r\n",heap -> array [i]);
  147. 	}
  148. }
  149.  
Success #stdin #stdout 0s 2296KB
comments (?)
stdin
copy 
insert 15
print
insert 4
print
insert 8
print
insert 9
print
insert 2
print
insert 18
print
extract
print
extract
print
extract
print
extract
print
extract
print
extract
print
extract
print
bye
stdout
copy 
18
18
18
18
18
18
https://ideone.com/x5QTUq
language:
C (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!