Prim MST in C++

prim.cpp

#include <iostream>
#include <ctime>
#include <cstdio>
#include <cstdlib>

#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define INF 1000000

using namespace std;

void swap(int &x, int &y) {
	int c = x;
	x = y;
	y = c;
}

typedef struct ed {
	int w;
	int v1, v2;
} Edge;

void swap(Edge &x, Edge &y) {
	swap(x.w, y.w);
	swap(x.v1, y.v1);
	swap(x.v2, y.v2);
}

class Heap {
	public:
	Edge a[1000];
	int heapsize;

	Heap(Edge arr[], int x, int y) {
		heapsize = 0;
		for (int i = x; i <= y; i++) {
			a[heapsize++].w = arr[i].w;
			a[heapsize++].v1 = arr[i].v1;
			a[heapsize++].v2 = arr[i].v2;
		}
	}
	
	Heap() {
		heapsize = 0;
	}

	void heapify(int i) {
		int l = 2 * i + 1;
		int r = 2 * i + 2;
		
		int min = i;
		if (l < heapsize && a[l].w < a[i].w) {
			min = l;
		} else {
			min = i;
		}

		if (r < heapsize && a[r].w < a[min].w) {
			min = r;
		}

		if (min != i) {
			swap(a[i], a[min]);
			heapify(min);
		}
	}
	
	void buildHeap() {
		for (int i = (heapsize - 1) / 2; i >= 0; i--) {
			heapify(i);
		}
	}

	Edge deleteRoot() {
		if (heapsize <= 0) {
			Edge e;
			e.w = e.v1 = e.v2 = -1;
			return e;
		}

		Edge tmp = a[0];
		a[0] = a[heapsize - 1];
		heapsize--;
		heapify(0);

		return tmp;
	}

	void upHeap(int i) {
		while (i > 0) {
			int parent = (i - 1) / 2;
			if (a[parent].w > a[i].w) {
				swap(a[parent], a[i]);
			}
			i = parent;
		}
	}

	void insert(Edge val) {
		a[heapsize].w = val.w;
		a[heapsize].v1 = val.v1;
		a[heapsize].v2 = val.v2;
		heapsize++;
		upHeap(heapsize - 1);
	}
};

class PQueue {
	public:
	Heap *heap;

	PQueue() {
		heap = new Heap();
	}

	void enqueue(Edge val) {
		heap->insert(val);
	}

	Edge dequeue() {
		return heap->deleteRoot();
	}

	Edge front() {
		return heap->a[0];
	}

	int size() {
		return heap->heapsize;
	}
};

/*void heapSort(int a[], int x, int y) {
	if (x >= y) return;

	Heap *heap = new Heap(a, x, y);
	heap->buildHeap();
	
	for (int i = x; i <= y; i++) {
		a[i] = heap->deleteRoot();
	}
}*/

bool isSorted(int a[], int x, int y) {
	if (x < y) {
		int min = a[x];

		for (int i = x + 1; i <= y; i++) {
			if (min > a[i]) {
				return false;
			}
			min = MIN(min, a[i]);
		}
	}
	return true;
}

int main() {
	srand(time(NULL));

	PQueue *q = new PQueue();

	int n = 4, m = 5;
	
	cin >> n >> m;
	int graph[n][n];
	int mst[n][n];
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			mst[i][j] = INF;
			graph[i][j] = INF;
		}
	}

	for (int i = 0; i < m; i++) {
		int v1, v2, w;
		cin >> v1 >> v2 >> w;
		v1--;
		v2--;
		graph[v1][v2] = w;
		graph[v2][v1] = w;
	}
	
	bool set[n];
	for (int i = 0; i < n; i++) {
		set[i] = false;
	}

	set[0] = true;
	for (int i = 0; i < n; i++) {
		if (graph[0][i] < INF) {
			Edge e;
			e.w = graph[0][i];
			e.v1 = 0;
			e.v2 = i;
			q->enqueue(e);
		}
	}

	for (int i = 1; i < n; i++) {
		Edge min = q->dequeue();
		int v1 = min.v1;
		int v2 = min.v2;
		
		while (set[v1] && set[v2]) {
			min = q->dequeue();
			v1 = min.v1;
			v2 = min.v2;
		}
		if (set[v2] && !set[v1]) {
			swap(v1, v2);
		}

		set[v2] = true;
		for (int j = 0; j < n; j++) {
			if (graph[v2][j] < INF) {
				Edge e;
				e.w = graph[v2][j];
				e.v1 = j;
				e.v2 = v2;
				q->enqueue(e);
			}
		}

		cout << (v1 + 1) << " " << (v2 + 1) << " -- " << min.w << endl;
		mst[v1][v2] = min.w;
		mst[v2][v1] = min.w;
	}
}