online compiler and debugger for c/c++

#include <iostream> #include <vector> #include <list> #include <utility> // for pair<> #include <iomanip> // for setw() #include <cmath> // for floor #include <chrono> using namespace std; using namespace std::chrono; /////////////// MinHeap //////////////// struct HeapNode{ int key, element; HeapNode():key(0),element(0){}; HeapNode(int key, int element):key(key),element(element){}; }; class BinaryHeap{ private: vector<HeapNode> heap; void swap(struct HeapNode &p1, struct HeapNode &p2); int FindPosition(int node); int GetParentNode(int node){return std::floor(node/2);}; public: BinaryHeap(){heap.resize(1);}; BinaryHeap(int n){ heap.resize(n + 1); // to store vertex and its distance } // Min-Priority Queue void MinHeapify(int node, int length); void BuildMinHeap(vector<float> array); //argument changed to vector<float> void DecreaseKey(int node, int newKey); void MinHeapInsert(int node, int key); int ExtractMin(); int Minimum(){return heap[1].element;}; bool IsHeapEmpty(){return (heap.size()<=1);}; }; int BinaryHeap::FindPosition(int node){ int idx = 0; for (int i = 1; i < heap.size(); i++) { if (heap[i].element == node) { idx = i; } } return idx; } void BinaryHeap::MinHeapInsert(int node, int key){ heap.push_back(HeapNode(node,key)); DecreaseKey(node, key); } void BinaryHeap::DecreaseKey(int node, int newKey){ int index_node = FindPosition(node); // search the index of node if (newKey >= heap[index_node].key) { cout << "new key is not smaller than current key\n"; return; } heap[index_node].key = newKey; // update key // to check whether subtree fulfill minheap condition while (index_node > 1 && heap[GetParentNode(index_node)].key > heap[index_node].key) { swap(heap[index_node], heap[GetParentNode(index_node)]); index_node = GetParentNode(index_node); } } void BinaryHeap::swap(struct HeapNode &p1, struct HeapNode &p2){ struct HeapNode temp = p1; p1 = p2; p2 = temp; } int BinaryHeap::ExtractMin(){ if (IsHeapEmpty()) { std::cout << "error: heap is empty\n"; exit(-1); } int min = heap[1].element; // let min store the element, and return min // delete the first element/vertex heap[1] = heap[heap.size()-1]; // put the last element in the first position of heap heap.erase(heap.begin()+heap.size()-1); // delete the last element MinHeapify(1, (int)heap.size()); // rearrange heap since heap[1] has the biggest value return min; } void BinaryHeap::BuildMinHeap(std::vector<float> array){//argument changed to vector<float> // store array in heap (do not use heap[0]) for (int i = 0; i < array.size(); i++) { heap[i + 1].element = i; // let the idx in array as element heap[i + 1].key = array[i]; // let the value in array as key } for (int i = (int)heap.size()/2; i >= 1 ; i--) { MinHeapify(i, (int)heap.size()-1); // length-1, since heap start from 1 } } void BinaryHeap::MinHeapify(int node, int length){ int left = 2*node, // get the left child right = 2*node + 1, // get the right child smallest; // smallest will keep the smallest weight among vertices if (left <= length && heap[left].key < heap[node].key) smallest = left; else smallest = node; if (right <= length && heap[right].key < heap[smallest].key) smallest = right; if (smallest != node) { // if the node key is not the smallest swap(heap[smallest], heap[node]); // swap to get the smallest MinHeapify(smallest, length); // rearrange the heap tree } } /////////////// Prim's Algorithm ///////////////// static const int maxDistance = 100; class Graph_MST{ private: int num_vertex; vector<list<pair<int,float> > > AdjList; vector<int> predecessor; vector<float> distance; //vector<int> changed to vector<float> vector<bool> visited; void InitializeSingleSource(int Start); // Let Start as the begin point void PrintDataArray(vector<int> array); public: Graph_MST():num_vertex(0){}; Graph_MST(int n):num_vertex(n){ AdjList.resize(num_vertex); } void AddEdge(int from, int to, float weight); void Prim_MinQueue(int Start); friend class BinaryHeap; }; void Graph_MST::InitializeSingleSource(int Start){ distance.resize(num_vertex); predecessor.resize(num_vertex); for (int i = 0; i < num_vertex; i++) { distance[i] = maxDistance; predecessor[i] = -1; } distance[Start] = 0; // set the starting vertex distance as 0, ExtractMin begins from starting vertex } void Graph_MST::Prim_MinQueue(int Start){ InitializeSingleSource(Start); BinaryHeap minQueue(num_vertex); minQueue.BuildMinHeap(distance); // use minQueue to handle distance[] visited.resize(num_vertex, false); // initializa visited[] as {0,0,0,...,0} while (!minQueue.IsHeapEmpty()) { int u = minQueue.ExtractMin(); visited[u] = true; for (list<pair<int, float> >::iterator itr = AdjList[u].begin(); itr != AdjList[u].end(); itr++) { if (visited[(*itr).first] == false && (*itr).second < distance[(*itr).first]) { distance[(*itr).first] = (*itr).second; predecessor[(*itr).first] = u; minQueue.DecreaseKey((*itr).first, distance[(*itr).first]); } } } /////// print result ///////// cout << setw(3) << "v1" << " - " << setw(3) << "v2"<< " : weight\n"; int i = (Start+1)%num_vertex; while (i != Start) { cout << setw(3) << predecessor[i] << " - " << setw(3) << i << " : " << setw(3) << distance[i] <<"\n"; i = (++i)%num_vertex; // After 6, 6+1 = 7, error:bad_access } } void Graph_MST::AddEdge(int from, int to, float weight){ AdjList[from].push_back(std::make_pair(to,weight)); AdjList[to].push_back(std::make_pair(from,weight)); } int main(){ Graph_MST graph(12); graph.AddEdge(0, 1, 0.9); //ab graph.AddEdge(0, 2, 0.7); //ac graph.AddEdge(1, 3, 0.6); //bd graph.AddEdge(1, 6, 0.7); //bg graph.AddEdge(2, 3, 0.8); //cd graph.AddEdge(2, 4, 0.6); //ce graph.AddEdge(2, 5, 0.3); //cf graph.AddEdge(3, 7, 0.5); //dh graph.AddEdge(3, 5, 0.8); //df graph.AddEdge(3, 9, 0.1); //dj graph.AddEdge(4, 5, 0.5); //ef graph.AddEdge(5, 9, 0.2); //fj graph.AddEdge(5, 11, 0.3); //fh graph.AddEdge(6, 8, 0.7); //gi graph.AddEdge(7, 8, 0.4); //hi graph.AddEdge(7, 11, 0.5); //hl graph.AddEdge(7, 10, 0.3); //hk graph.AddEdge(8, 10, 0.7); //ik graph.AddEdge(8, 11, 0.8); //il graph.AddEdge(9, 11, 0.5); //jl graph.AddEdge(10, 11, 0.9); //kl cout << "MST found by Prim_MinQueue:\n"; auto start = high_resolution_clock::now(); graph.Prim_MinQueue(2); auto stop = high_resolution_clock::now(); auto duration = duration_cast<microseconds>(stop - start); cout << "Time taken by function: " << duration.count() << " microseconds" << endl; return 0; } //ref source: http://alrightchiu.github.io/SecondRound/minimum-spanning-treeprims-algorithm-using-min-priority-queue.html