Scribd
Upload
8 views

Heap Sort

Uploaded by

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

Heap Sort

Uploaded by

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

NAME : AMAN VERMA

MIS : 612303196

TOPIC : Heap sort

HEADER.h

typedef struct {

int *arr;

int size;

int capacity;

} MinHeap;

// Function declarations

MinHeap* createMinHeap(int capacity);

void insertHeap(MinHeap *heap, int value);

int extractMin(MinHeap *heap);

void freeHeap(MinHeap *heap);

LOGIC.c

#include <stdio.h>

#include <stdlib.h>

#include "header.h"

void swap(int *a, int *b) {

int temp = *a;

*a = *b;
*b = temp;

void minHeapify(MinHeap *heap, int i) {

int smallest = i;

int left = 2 * i + 1;

int right = 2 * i + 2;

if (left < heap->size && heap->arr[left] < heap->arr[smallest])

smallest = left;

if (right < heap->size && heap->arr[right] < heap->arr[smallest])

smallest = right;

if (smallest != i) {

swap(&heap->arr[i], &heap->arr[smallest]);

minHeapify(heap, smallest);

MinHeap* createMinHeap(int capacity) {

MinHeap *heap = (MinHeap*) malloc(sizeof(MinHeap));

heap->size = 0;

heap->capacity = capacity;

heap->arr = (int*) malloc(capacity * sizeof(int));

return heap;

}
void insertHeap(MinHeap *heap, int value) {

if (heap->size == heap->capacity) {

printf("Heap overflow\n");

return;

int i = heap->size++;

heap->arr[i] = value;

while (i != 0 && heap->arr[(i - 1) / 2] > heap->arr[i]) {

swap(&heap->arr[i], &heap->arr[(i - 1) / 2]);

i = (i - 1) / 2;

int extractMin(MinHeap *heap) {

if (heap->size <= 0)

return -1;

if (heap->size == 1)

return heap->arr[--heap->size];

int root = heap->arr[0];

heap->arr[0] = heap->arr[--heap->size];

minHeapify(heap, 0);
return root;

void freeHeap(MinHeap *heap) {

free(heap->arr);

free(heap);

MAIN.c

#include <stdio.h>

#include <stdlib.h>

#include <fcntl.h>

#include <unistd.h>

#include "header.h"

#define BUFFER_SIZE 1024

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

if (argc != 2) {

const char *msg = "Usage: ./heapsort <filename>\n";

write(STDERR_FILENO, msg, sizeof(msg));

return 1;

}
int fd = open(argv[1], O_RDONLY);

if (fd == -1) {

perror("Error opening file");

return 1;

char buffer[BUFFER_SIZE];

int bytesRead = read(fd, buffer, sizeof(buffer) - 1);

if (bytesRead == -1) {

perror("Error reading file");

close(fd);

return 1;

buffer[bytesRead] = '\0';

close(fd);

int capacity = 100;

MinHeap *heap = createMinHeap(capacity);

int number;

char *ptr = buffer;

while (sscanf(ptr, "%d", &number) == 1) {

insertHeap(heap, number);

while (*ptr != ' ' && *ptr != '\n' && *ptr != '\0') {

ptr++;

}
if (*ptr == '\0') break;

ptr++;

const char *sorted_msg = "Sorted integers:\n";

write(STDOUT_FILENO, sorted_msg, sizeof("Sorted integers:\n") - 1);

char num_str[12];

while (heap->size > 0) {

int sorted_number = extractMin(heap);

int len = snprintf(num_str, sizeof(num_str), "%d ", sorted_number);

write(STDOUT_FILENO, num_str, len);

write(STDOUT_FILENO, "\n", 1);

freeHeap(heap);

return 0;

Numbers.txt
Output :

You might also like