| | | 1 | | /* This file is a template for heap.c. Content will be filled by yagiz on 2025-12-29. */ |
| | | 2 | | #include <stdio.h> |
| | | 3 | | #include "heap.h" |
| | | 4 | | |
| | | 5 | | // Helper: Bubble Up (Moves a node UP to its correct position) |
| | 109 | 6 | | static void bubbleUp(Heap *h, int index) { |
| | 114 | 7 | | while (index > 0) { |
| | 105 | 8 | | int parentIndex = (index - 1) / 2; |
| | | 9 | | // Max-Heap Logic: Parent should be greater. |
| | | 10 | | // Tie-Breaker: If Priorities are EQUAL, Older Timestamp (smaller value) wins. |
| | 105 | 11 | | bool parentIsSmaller = h->data[parentIndex].priority < h->data[index].priority; |
| | 205 | 12 | | bool equalButNewer = (h->data[parentIndex].priority == h->data[index].priority) && |
| | 100 | 13 | | (h->data[parentIndex].timestamp > h->data[index].timestamp); |
| | | 14 | | |
| | 105 | 15 | | if (parentIsSmaller || equalButNewer) { |
| | | 16 | | // SWAP |
| | 5 | 17 | | Task temp = h->data[parentIndex]; |
| | 5 | 18 | | h->data[parentIndex] = h->data[index]; |
| | 5 | 19 | | h->data[index] = temp; |
| | | 20 | | // Move up |
| | 5 | 21 | | index = parentIndex; |
| | | 22 | | } else { |
| | | 23 | | break; // Order is correct |
| | | 24 | | } |
| | | 25 | | } |
| | 109 | 26 | | } |
| | | 27 | | |
| | | 28 | | // Helper: Heapify / Bubble Down (Moves a node DOWN to its correct position) |
| | 10 | 29 | | static void heapify(Heap *h, int index) { |
| | 10 | 30 | | int largest = index; |
| | 10 | 31 | | int left = 2 * index + 1; |
| | 10 | 32 | | int right = 2 * index + 2; |
| | | 33 | | |
| | | 34 | | // Check Left Child |
| | 10 | 35 | | if (left < h->count) { |
| | 3 | 36 | | bool leftIsBigger = h->data[left].priority > h->data[largest].priority; |
| | 3 | 37 | | bool leftEqualButOlder = (h->data[left].priority == h->data[largest].priority) && |
| | 0 | 38 | | (h->data[left].timestamp < h->data[largest].timestamp); // Smaller timestamp = Older |
| | | 39 | | |
| | 3 | 40 | | if (leftIsBigger || leftEqualButOlder) { |
| | 2 | 41 | | largest = left; |
| | | 42 | | } |
| | | 43 | | } |
| | | 44 | | |
| | | 45 | | // Check Right Child |
| | 10 | 46 | | if (right < h->count) { |
| | 0 | 47 | | bool rightIsBigger = h->data[right].priority > h->data[largest].priority; |
| | 0 | 48 | | bool rightEqualButOlder = (h->data[right].priority == h->data[largest].priority) && |
| | 0 | 49 | | (h->data[right].timestamp < h->data[largest].timestamp); |
| | | 50 | | |
| | 0 | 51 | | if (rightIsBigger || rightEqualButOlder) { |
| | 0 | 52 | | largest = right; |
| | | 53 | | } |
| | | 54 | | } |
| | | 55 | | |
| | | 56 | | // Swap and Recursive Call |
| | 10 | 57 | | if (largest != index) { |
| | 2 | 58 | | Task temp = h->data[index]; |
| | 2 | 59 | | h->data[index] = h->data[largest]; |
| | 2 | 60 | | h->data[largest] = temp; |
| | 2 | 61 | | heapify(h, largest); |
| | | 62 | | } |
| | 10 | 63 | | } |
| | | 64 | | |
| | 5 | 65 | | void initHeap(Heap *h) { |
| | 5 | 66 | | h->count = 0; |
| | 5 | 67 | | } |
| | | 68 | | |
| | | 69 | | // INSERT |
| | 109 | 70 | | bool insertHeap(Heap *h, Task task) { |
| | 109 | 71 | | if (h->count >= MAX_HEAP_SIZE) { |
| | 1 | 72 | | printf("ERROR: Heap is full! Cannot add Task-%d\n", task.id); |
| | 1 | 73 | | return false; |
| | | 74 | | } |
| | | 75 | | |
| | | 76 | | // 1. Add to end |
| | 108 | 77 | | h->data[h->count] = task; |
| | | 78 | | // 2. Bubble Up |
| | 108 | 79 | | bubbleUp(h, h->count); |
| | | 80 | | // 3. Increment Count |
| | 108 | 81 | | h->count++; |
| | 108 | 82 | | printf("Task Added: ID-%d [P:%d]\n", task.id, task.priority); |
| | 108 | 83 | | return true; |
| | | 84 | | } |
| | | 85 | | |
| | | 86 | | // EXTRACT MAX |
| | 8 | 87 | | bool extractMax(Heap *h, Task *outTask) { |
| | 8 | 88 | | if (h->count == 0) { |
| | 1 | 89 | | printf("ERROR: Heap is empty!\n"); |
| | 1 | 90 | | return false; |
| | | 91 | | } |
| | | 92 | | |
| | | 93 | | // 1. Get Root (Max Priority) |
| | 7 | 94 | | *outTask = h->data[0]; |
| | | 95 | | // 2. Move last element to root |
| | 7 | 96 | | h->data[0] = h->data[h->count - 1]; |
| | 7 | 97 | | h->count--; |
| | | 98 | | // 3. Heaterify (Bubble Down) |
| | 7 | 99 | | heapify(h, 0); |
| | | 100 | | // printf("Task Extracted: ID-%d [P:%d]\n", outTask->id, outTask->priority); |
| | 7 | 101 | | return true; |
| | | 102 | | } |
| | | 103 | | |
| | | 104 | | // UPDATE PRIORITY (Dynamic Update) |
| | 3 | 105 | | bool updatePriority(Heap *h, int task_id, int new_priority) { |
| | 3 | 106 | | int index = -1; |
| | | 107 | | |
| | | 108 | | // 1. Find the task |
| | 5 | 109 | | for(int i = 0; i < h->count; i++) { |
| | 4 | 110 | | if(h->data[i].id == task_id) { |
| | 2 | 111 | | index = i; |
| | 2 | 112 | | break; |
| | | 113 | | } |
| | | 114 | | } |
| | | 115 | | |
| | 3 | 116 | | if(index == -1) { |
| | 1 | 117 | | printf("ERROR: Task-%d not found!\n", task_id); |
| | 1 | 118 | | return false; |
| | | 119 | | } |
| | | 120 | | |
| | 2 | 121 | | int old_priority = h->data[index].priority; |
| | 2 | 122 | | h->data[index].priority = new_priority; |
| | 2 | 123 | | printf("Task-%d Priority Updated: %d -> %d\n", task_id, old_priority, new_priority); |
| | | 124 | | |
| | | 125 | | // 2. Re-balance |
| | 2 | 126 | | if (new_priority > old_priority) { |
| | 1 | 127 | | bubbleUp(h, index); |
| | | 128 | | } else { |
| | 1 | 129 | | heapify(h, index); |
| | | 130 | | } |
| | | 131 | | |
| | 2 | 132 | | return true; |
| | | 133 | | } |
| | | 134 | | |
| | 2 | 135 | | int getHeapSize(Heap *h) { |
| | 2 | 136 | | return h->count; |
| | | 137 | | } |