Hey, I have to code a min-heap, along with other things to help compute minimum spanning tree.

I coded up the min-heap pretty easily and I have no compile errors, however my delete fix up does not seem to be working properly.

For example, I insert these ints into an empty min heap:

10, 9, 7, 2, 5, 3, 8, 4.

I get the min-heap:

2, 4, 3, 5, 7, 9, 8, 10

After the first extract minimum call I get the min-heap:

3, 4, 8, 5, 7, 9, 10

Which is correct, however, if I call min-heap again I get this heap:

8, 4, 10, 5, 7, 9

Which is incorrect, I've check my code and I still can't find the problem.

My min-heap consist of "edges" and not ints. An edge is a class that consist of 3 ints that represent two vertices and a cost. My min-heap is sorted by cost.

Here is the header file:

Here is my heap.cpp file:Code:/* * File: heap.h * Author: Owner * * Created on April 24, 2010, 10:51 PM */ #ifndef _HEAP_H #define _HEAP_H #include <vector> #include "edge.h" using namespace std; class min_heap { public: min_heap(int size); ~min_heap(); int get_min(); void extract_min(); bool isEmpty(); void insert(edge newEdge); void bottom_up(int i); void top_down(int i); void display(); void heapify(int i); vector<edge> theEdges; // private: int heapSize; int arraySize; int* data; int parent(int i); int lchild(int i); int rchild(int i); }; #endif /* _HEAP_H */

The deletion fix up was the "top_down" function, but that didn't seem to work. So I created the "heapify" function, and that gives me the problem that I stated above. Any help at all would be appreciated.Code:#include <vector> #include "heap.h" #include "edge.h" #include <string> #include <iostream> using namespace std; min_heap::min_heap(int size) { arraySize = 0; heapSize = 0; theEdges.resize(size); } min_heap::~min_heap() { delete[] data; } int min_heap::parent(int i) { //return i/2; return (i-1)/2; } int min_heap::lchild(int i) { //return 2*i; return 2*(i+1); } int min_heap::rchild(int i) { //return 2*i+1; return 2*i+2; } bool min_heap::isEmpty() { return (heapSize == 0); } int min_heap::get_min() { if(isEmpty()) ; // throw string("empty the heap is"); else return theEdges[0].cost; } void min_heap::bottom_up(int i) { int p; int temp; if(i != 0) { p = parent(i); if(theEdges[p].cost > theEdges[i].cost) { temp = theEdges[p].cost; theEdges[p].cost = theEdges[i].cost; theEdges[i].cost = temp; bottom_up(p); } } } void min_heap::top_down(int i) { int min_element; int temp; int left = lchild(i); int right = rchild(i); if(right >= heapSize) { if(left >= heapSize) return; else min_element = left; } else { if(theEdges[left].cost <= theEdges[right].cost) min_element = left; else min_element = right; } if(theEdges[i].cost> theEdges[min_element].cost) { temp = data[min_element]; theEdges[min_element].cost = theEdges[i].cost; theEdges[i].cost = temp; top_down(min_element); } } void min_heap:: insert(edge newEdge) { theEdges[heapSize] = newEdge; //top_down(heapSize-1); bottom_up(heapSize); heapSize++; } void min_heap::extract_min() { theEdges[0] = theEdges[heapSize-1]; heapSize--; if(heapSize> 0) { heapify(0); //top_down(0); } } void min_heap::display() { for(int i = 0; i < heapSize; i++) cout<< "i is: " << i << ", data is: " << theEdges[i].cost << ", " << endl;; } void min_heap:: heapify(int i) { int left = lchild(i); int right = rchild(i); int smallest; int temp; if(left <= heapSize && theEdges[left].cost < theEdges[i].cost) smallest = left; else smallest = i; if(right <= heapSize && theEdges[right].cost < theEdges[smallest].cost) smallest = right; if(smallest != i) { temp = theEdges[smallest].cost; theEdges[smallest].cost = theEdges[i].cost; theEdges[i].cost = temp; heapify(smallest); } }

Here is the edge.h file if needed:

Code:/* * File: edge.h * Author: Owner * * Created on April 28, 2010, 3:30 PM */ #ifndef _EDGE_H #define _EDGE_H class edge { public: int u; int v; int cost; edge() { u = -1; v = -1; cost = -1; } edge (int vertex1,int vertext2,int theCost) { u = vertex1; v = vertext2; cost = theCost; } }; #endif /* _EDGE_H */