STL c++ heap_sort

sort by attribute

Page 1 of 1

3 Replies - 1480 Views - Last Post: 09 December 2010 - 04:57 PM Rate Topic: -----

#1 kamikaze942  Icon User is offline

  • New D.I.C Head

Reputation: -1
  • View blog
  • Posts: 24
  • Joined: 05-November 09

STL c++ heap_sort

Posted 08 December 2010 - 09:48 AM

looking at using the heap_sort under the stl library for my project, looking at the example from...

cpluscplus.com

i see they are sorting from the vector<type>, as in their example vector<int>. i want to sort from an attribute of a type Vertex.. so..


vector<Vertex*> heap(G->V, G->V+6) // 6 vertex  G is graph, V is array 
make_heap(heap.begin(), heap.end());
sort_heap(heap.begin(), heap.end()); 


for(int i = 0; i<heap.size(); i++) cout<<" "<<heap[i]; cout<<endl;



prints out a bunch of gibberish, if i print heap[i]->id then i can see the order but it's not sorting them by the distanceFromSource attritube that I want. Actually I have no idea what order it is sorting them. Anyone know how to sort them by an attribute of that type? should i do a work around or abandon the stl heap_sort altogether?

Is This A Good Question/Topic? 0
  • +

Replies To: STL c++ heap_sort

#2 kamikaze942  Icon User is offline

  • New D.I.C Head

Reputation: -1
  • View blog
  • Posts: 24
  • Joined: 05-November 09

Re: STL c++ heap_sort

Posted 08 December 2010 - 09:57 AM

i think i just post my problems sometimes just so I can think about things when i write them down, haha.
SOLVED

struct DistanceSort{

   bool operator() {Vertex* vert1, Vertex* vert2)
    { 
          return vert1->distanceFromSource < vert2->distanceFromSource;
    }
}; 


sort_heap(heap.begin(), heap.end(), DistanceSort());


This post has been edited by kamikaze942: 08 December 2010 - 09:57 AM

Was This Post Helpful? 0
  • +
  • -

#3 kamikaze942  Icon User is offline

  • New D.I.C Head

Reputation: -1
  • View blog
  • Posts: 24
  • Joined: 05-November 09

Re: STL c++ heap_sort

Posted 08 December 2010 - 06:35 PM

ok, i'm still having some problems with this sort. I read at one place that it might be a problem with the actual heap_sort code itself from microsoft, but was wondering if any of you might know a fix.

what i'm doing is...

vector<Vertex*> heap(graph->V, graph->V+6);
vector<Vertex*> S;
make_heap(heap.begin(), heap.end());
sort_heap(heap.begin(), heap.end(), DistanceSort()); // for distance from sort for vertexes

graph->RelaxEdge(heap[0]);
S.push_back(heap[0]); // add vertex to set S
//must reverse heap, as DistanceSort and popback conflict 
reverse(heap.begin(), heap.end());

//optional for printing the vertices and weights 
for(unsigned i = 0; i<heap.size(); i++) cout<<" " <<heap[i]->id<<" "<<heap[i]->distanceFromSource<<endl;

heap.pop_back();
make_heap(heap.begin(), heap.end());
//sort_heap(heap.begin(), heap.end(), DistanceSort());  <---   when i sort again i get invalid heap 
reverse(heap.begin(), heap.end());// reversing again to pull heap[0] 




as you can see in the code when i try to sort again it gives me an error of
expression: invalid heap

really don't want to go back and redo all my binary heap code...
Was This Post Helpful? 0
  • +
  • -

#4 kamikaze942  Icon User is offline

  • New D.I.C Head

Reputation: -1
  • View blog
  • Posts: 24
  • Joined: 05-November 09

Re: STL c++ heap_sort

Posted 09 December 2010 - 04:57 PM

SOLVED

used sort(heap.begin(), heap.end(), DistanceSort());

instead of sort_heap()

"if it works, it works"
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1