Min-heap extract min not working correctly

[Uni616]

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:

/* 
 * 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 */

Here is my heap.cpp file:

#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);
    }


    
}

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.

Here is the edge.h file if needed:

/* 
 * 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 */