-
Notifications
You must be signed in to change notification settings - Fork 1
/
heap.c
112 lines (86 loc) · 3.32 KB
/
heap.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
#include "Heap.h"
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
//definiitions of functions related to heap:
// Structure to represent a min heap node
struct MinHeapNode *newMinHeapNode(int v, int dist) {
struct MinHeapNode *minHeapNode = (struct MinHeapNode *)malloc(sizeof(struct MinHeapNode));
minHeapNode->v = v;
minHeapNode->dist = dist;
return minHeapNode;
}
// Structure to represent a min heap
struct MinHeap *createMinHeap(int capacity) {
struct MinHeap *minHeap = (struct MinHeap *)malloc(sizeof(struct MinHeap));
minHeap->pos = (int *)malloc(capacity * sizeof(int));
minHeap->size = 0;
minHeap->capacity = capacity;
minHeap->array = (struct MinHeapNode **)malloc(capacity * sizeof(struct MinHeapNode *));
return minHeap;
}
//A utility function to swap two nodes of min heap. Required for min heapify.
void swapMinHeapNode(struct MinHeapNode **a, struct MinHeapNode **b) {
struct MinHeapNode *t = *a;
*a = *b;
*b = t;
}
// A standard function to heapify at given idx
// This function also updates position of nodes when they are swapped.
void minHeapify(struct MinHeap *minHeap, int idx) {
int smallest, left, right;
smallest = idx;
left = 2 * idx + 1;
right = 2 * idx + 2;
if (left < minHeap->size && minHeap->array[left]->dist < minHeap->array[smallest]->dist)
smallest = left;
if (right < minHeap->size && minHeap->array[right]->dist < minHeap->array[smallest]->dist)
smallest = right;
if (smallest != idx)
{
struct MinHeapNode *smallestNode = minHeap->array[smallest];
struct MinHeapNode *idxNode = minHeap->array[idx];
minHeap->pos[smallestNode->v] = idx;
minHeap->pos[idxNode->v] = smallest;
swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]);
minHeapify(minHeap, smallest);
}
}
//A utility function to check if the given minHeap is empty or not
int isEmpty(struct MinHeap *minHeap) {
return minHeap->size == 0;
}
// Standard function to extract minimum node from heap
struct MinHeapNode *extractMin(struct MinHeap *minHeap) {
if (isEmpty(minHeap))
return NULL;
struct MinHeapNode *root = minHeap->array[0];
struct MinHeapNode *lastNode = minHeap->array[minHeap->size - 1];
minHeap->array[0] = lastNode;
minHeap->pos[root->v] = minHeap->size - 1;
minHeap->pos[lastNode->v] = 0;
--minHeap->size;
minHeapify(minHeap, 0);
return root;
}
// Function to decrease key value of a given vertex v. This function
// uses pos[] of min heap to get the current index of node in min heap
void decreaseKey(struct MinHeap *minHeap, int v, int dist) {
int i = minHeap->pos[v];
minHeap->array[i]->dist = dist;
while (i && minHeap->array[i]->dist < minHeap->array[(i - 1) / 2]->dist)
{
minHeap->pos[minHeap->array[i]->v] = (i - 1) / 2;
minHeap->pos[minHeap->array[(i - 1) / 2]->v] = i;
swapMinHeapNode(&minHeap->array[i], &minHeap->array[(i - 1) / 2]);
i = (i - 1) / 2;
}
}
// A utility function to check if a given vertex
// 'v' is in min heap or not
bool isInMinHeap(struct MinHeap *minHeap, int v)
{
if (minHeap->pos[v] < minHeap->size)
return true;
return false;
}