Scribd
Upload
22 views2 pages

Code 2

The document contains C code that implements a min-heap data structure with functions for initialization, deletion, insertion, and extraction of elements. It reads integers from an input file, stores them in a heap, and then writes the sorted integers to an output file. The code also includes error handling for file operations.

Uploaded by

S
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
22 views2 pages

Code 2

The document contains C code that implements a min-heap data structure with functions for initialization, deletion, insertion, and extraction of elements. It reads integers from an input file, stores them in a heap, and then writes the sorted integers to an output file. The code also includes error handling for file operations.

Uploaded by

S
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
You are on page 1/ 2

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
struct Heap {
size_t size;
int* elems;
};
typedef struct Heap Heap;

void heap_init(Heap* heap, size_t n){


heap->size = 0;
heap->elems = (int*)malloc(sizeof(int)*(n+1));
}

void heap_del(Heap* heap) {


heap->size = 0;
free(heap->elems);
free(heap);
}

void push(Heap* heap,int x) {


int pos = ++heap->size;
heap->elems[pos] = x;
while (pos>1 && heap->elems[pos/2] > x) {
heap->elems[pos/2] ^= heap->elems[pos];
heap->elems[pos] ^= heap->elems[pos/2];
heap->elems[pos / 2] ^= heap->elems[pos];

pos /= 2;
}
}

void heapify(Heap* heap, int pos) {


while (pos * 2 <= heap->size && (heap->elems[pos] > heap->elems[pos * 2] ||
heap->elems[pos] > heap->elems[pos * 2 + 1])) {
if (pos * 2 + 1 <= heap->size && heap->elems[pos * 2 + 1] < heap-
>elems[pos * 2]) {
heap->elems[pos] ^= heap->elems[pos * 2 + 1];
heap->elems[pos * 2 + 1] ^= heap->elems[pos];
heap->elems[pos] ^= heap->elems[pos * 2 + 1];
pos = pos * 2 + 1;
}
else {
heap->elems[pos] ^= heap->elems[pos * 2];
heap->elems[pos * 2] ^= heap->elems[pos];
heap->elems[pos] ^= heap->elems[pos * 2];
pos *= 2;
}
}
}

int pop(Heap* heap) {


int top = heap->elems[1];
heap->elems[1] = heap->elems[heap->size--];
heapify(heap, 1);
return top;
}

void exit1(FILE* file1, FILE* file2) {


if (file2 != NULL)fclose(file2);
if (file1 != NULL)fclose(file1);
}

int main() {
FILE* file_in = fopen("in.txt", "r");
FILE* file_out = fopen("out.txt", "w");
if (file_in == NULL || file_out == NULL) { exit1(file_in, file_out); return
0; }
int n;
fscanf(file_in, "%d", &n);
Heap* heap = (Heap*)malloc(sizeof(Heap));
heap_init(heap, n);
for (int i = 1; i <= n; i++) {
int x;
fscanf(file_in, "%d", &x);
push(heap, x);
}
for (int i = 1; i <= n; i++) {
fprintf(file_out, "%d ", pop(heap));
}
heap_del(heap);
exit1(file_in, file_out);
return 0;
}

You might also like