@candh/

ultraHeap [max heap]

C

ZALIMAA COCA COLA PILLA DEE

fork
loading
Files
  • main.c

This Plugin Crashed!

Error: Error: must not create an existing file {"type":"CREATE_FILE","wid":"0.5816975403939655","path":"main.c","file":{"path":"main.c","content":{"asEncoding":{"base64":"Ly8gcGxlYXNlIHNlZSB0aGlzIHRvbwovLyBodHRwczovL3d3dy5wcm9ncmFtaXouY29tL2RzYS9oZWFwLXNvcnQKI2luY2x1ZGUgPHN0ZGxpYi5oPgojaW5jbHVkZSA8c3RkaW8uaD4KCnR5cGVkZWYgc3RydWN0IEhlYXAgSGVhcDsKc3RydWN0IEhlYXAgewoJaW50ICogYXJyOwoJaW50IGhlYXBfc2l6ZTsKCWludCBzaXplOwkKfTsKCnZvaWQgc3dhcChpbnQgKiBhLCBpbnQgKiBiKSB7CglpbnQgdGVtcCA9ICphOwoJKmEgPSAqYjsKCSpiID0gdGVtcDsKfQoKaW50IHBhcmVudChpbnQgaSkgewoJcmV0dXJuIChpIC0gMSkgLyAyOwp9CgppbnQgbGVmdChpbnQgaSkgewoJcmV0dXJuICgyICogaSArIDEpOwp9CgppbnQgcmlnaHQoaW50IGkpIHsKCXJldHVybiAoMiAqIGkgKyAyKTsKfQoKSGVhcCAqIGNvbnN0cnVjdChpbnQgc2l6ZSkgewoJSGVhcCAqIGhlYXAgPSBtYWxsb2Moc2l6ZW9mKEhlYXApKTsKCWhlYXAtPmhlYXBfc2l6ZSA9IDA7CgloZWFwLT5zaXplID0gc2l6ZTsKCgloZWFwLT5hcnIgPSBtYWxsb2Moc2l6ZW9mKGludCkgKiBzaXplKTsKCXJldHVybiBoZWFwOwp9Cgp2b2lkIGluc2VydChIZWFwICogaGVhcCwgaW50IGVsKSB7CiAgaWYgKGhlYXAtPnNpemUgPT0gaGVhcC0+aGVhcF9zaXplKSB7CiAgICBwcmludGYoIk1heEhlYXAgaXMgZnVsbFxuIik7CiAgfQoKICBoZWFwLT5oZWFwX3NpemUrKzsKICBpbnQgaSA9IGhlYXAtPmhlYXBfc2l6ZSAtIDE7CiAgaGVhcC0+YXJyW2ldID0gZWw7CgogIHdoaWxlIChpICE9IDAgJiYgaGVhcC0+YXJyW3BhcmVudChpKV0gPCBoZWFwLT5hcnJbaV0pIHsKICAgIHN3YXAoJmhlYXAtPmFycltpXSwgJmhlYXAtPmFycltwYXJlbnQoaSldKTsKICAgIGkgPSBwYXJlbnQoaSk7CiAgfQp9Cgp2b2lkIGhlYXBpZnkoSGVhcCAqIGhlYXAsIGludCBpKSB7CiAgaW50IGxlZnRfID0gbGVmdChpKTsKICBpbnQgcmlnaHRfID0gcmlnaHQoaSk7CiAgaW50IGxhcmdlc3QgPSBpOwoKICBpZiAobGVmdF8gPCBoZWFwLT5oZWFwX3NpemUgJiYgaGVhcC0+YXJyW2xlZnRfXSA+IGhlYXAtPmFycltsYXJnZXN0XSkgewogICAgbGFyZ2VzdCA9IGxlZnRfOwogIH0KICBpZiAocmlnaHRfIDwgaGVhcC0+aGVhcF9zaXplICYmIGhlYXAtPmFycltyaWdodF9dID4gaGVhcC0+YXJyW2xhcmdlc3RdKSB7CiAgICBsYXJnZXN0ID0gcmlnaHRfOwogIH0KCiAgaWYgKGxhcmdlc3QgIT0gaSkgewogICAgc3dhcCgmaGVhcC0+YXJyW2ldLCAmaGVhcC0+YXJyW2xhcmdlc3RdKTsKICAgIGhlYXBpZnkoaGVhcCwgbGFyZ2VzdCk7CiAgfQp9Cgp2b2lkIGRlbGV0ZShIZWFwICogaGVhcCkgewogIGlmIChoZWFwLT5oZWFwX3NpemUpIHsKICAgIC8vIG1vdmUgdGhlIGxlYWYgbm9kZSB0byB0aGUgcm9vdCBub2RlCgogICAgaGVhcC0+YXJyWzBdID0gaGVhcC0+YXJyWy0tKGhlYXAtPmhlYXBfc2l6ZSldOwogICAgaGVhcGlmeShoZWFwLCAwKTsKICB9IGVsc2UgewogICAgcHJpbnRmKCJNYXhIZWFwIGlzIGVtcHR5XG4iKTsKICB9Cn0KCnZvaWQgcHJpbnQoSGVhcCAqIGhlYXApIHsKICBpbnQgaTsKICBmb3IgKGkgPSAwOyBpIDwgaGVhcC0+c2l6ZTsgaSsrKSB7CiAgICBwcmludGYoIiVkICIsIGhlYXAtPmFycltpXSk7CiAgfQogIAogIHByaW50ZigiXG4iKTsKfQoKCnZvaWQgaGVhcF9zb3J0KEhlYXAgKiBoZWFwKSB7CglpZiAoaGVhcC0+aGVhcF9zaXplKSB7CgoJCXdoaWxlIChoZWFwLT5oZWFwX3NpemUgPiAwKSB7CgkJCWludCB0ZW1wID0gaGVhcC0+YXJyWzBdOwoJCSAgCgkJICBoZWFwLT5hcnJbMF0gPSBoZWFwLT5hcnJbaGVhcC0+aGVhcF9zaXplIC0gMV07CgoJCSAgaGVhcC0+YXJyW2hlYXAtPmhlYXBfc2l6ZSAtIDFdID0gdGVtcDsKCgkJICAvLyBwcmludChoZWFwKTsKCQkgIGhlYXAtPmhlYXBfc2l6ZS0tOwoJCSAgaGVhcGlmeShoZWFwLCAwKTsKCQl9Cgl9Cn0KCmludCBtYWluKCkgewoJSGVhcCAqIGhlYXAgPSBjb25zdHJ1Y3QoNik7CgogIGluc2VydChoZWFwLCAxMik7CiAgaW5zZXJ0KGhlYXAsIDYpOwogIGluc2VydChoZWFwLCAxMCk7CiAgaW5zZXJ0KGhlYXAsIDUpOwogIGluc2VydChoZWFwLCAxKTsKICBpbnNlcnQoaGVhcCwgOSk7CgogIC8vIHByaW50KGhlYXApOwogIC8vIGRlbGV0ZShoZWFwKTsKICAvLyBwcmludChoZWFwKTsKICAvLyBoZWFwX3NvcnQoaGVhcCk7CiAgcHJpbnQoaGVhcCk7CgogIC8vIGRlbGV0ZShoZWFwKTsKICAvLyBwcmludChoZWFwKTsKCn0="},"asBuffer":null},"loaded":true}}
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);

}