Files
  • main.c
main.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
// please see this too
// https://www.programiz.com/dsa/heap-sort
#include <stdlib.h>
#include <stdio.h>

typedef struct Heap Heap;
struct Heap {
	int * arr;
	int heap_size;
	int size;	
};

void swap(int * a, int * b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}

int parent(int i) {
	return (i - 1) / 2;
}

int left(int i) {
	return (2 * i + 1);
}

int right(int i) {
	return (2 * i + 2);
}

Heap * construct(int size) {
	Heap * heap = malloc(sizeof(Heap));
	heap->heap_size = 0;
	heap->size = size;

	heap->arr = malloc(sizeof(int) * size);
	return heap;
}

void insert(Heap * heap, int el) {
  if (heap->size == heap->heap_size) {
    printf("MaxHeap is full\n");
  }

  heap->heap_size++;
  int i = heap->heap_size - 1;
  heap->arr[i] = el;

  while (i != 0 && heap->arr[parent(i)] < heap->arr[i]) {
    swap(&heap->arr[i], &heap->arr[parent(i)]);
    i = parent(i);
  }
}

void heapify(Heap * heap, int i) {
  int left_ = left(i);
  int right_ = right(i);
  int largest = i;

  if (left_ < heap->heap_size && heap->arr[left_] > heap->arr[largest]) {
    largest = left_;
  }
  if (right_ < heap->heap_size && heap->arr[right_] > heap->arr[largest]) {
    largest = right_;
  }

  if (largest != i) {
    swap(&heap->arr[i], &heap->arr[largest]);
    heapify(heap, largest);
  }
}

void delete(Heap * heap) {
  if (heap->heap_size) {
    // move the leaf node to the root node

    heap->arr[0] = heap->arr[--(heap->heap_size)];
    heapify(heap, 0);
  } else {
    printf("MaxHeap is empty\n");
  }
}

void print(Heap * heap) {
  int i;
  for (i = 0; i < heap->size; i++) {
    printf("%d ", heap->arr[i]);
  }
  
  printf("\n");
}


void heap_sort(Heap * heap) {
	if (heap->heap_size) {

		while (heap->heap_size > 0) {
			int temp = heap->arr[0];
		  
		  heap->arr[0] = heap->arr[heap->heap_size - 1];

		  heap->arr[heap->heap_size - 1] = temp;

		  // print(heap);
		  heap->heap_size--;
		  heapify(heap, 0);
		}
	}
}

int main() {
	Heap * heap = construct(6);

  insert(heap, 12);
  insert(heap, 6);
  insert(heap, 10);
  insert(heap, 5);
  insert(heap, 1);
  insert(heap, 9);

  // print(heap);
  // delete(heap);
  // print(heap);
  // heap_sort(heap);
  print(heap);

  // delete(heap);
  // print(heap);

}